實機體驗,再天天抽M8女大生禁不起誘惑!按了..輕忽小中風,當心變殘障老伯送飲料 遭學生糾察...
2012-06-07 21:35:17 人氣(219) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][幾何] 833 - Water Falls

0
收藏
0
推薦


  Water Falls 

Consider the set of line segments P1, P2 and P3 of figure 1, representing the side view of a set of planes. What happens if some water falls (in the vertical direction and ignoring horizontal deviations created by kinetics) from source point Sa? It flows over the plane P3, to P1, finally falling on the ground at the point Ga. It is easy to see that, if the water is falling from source point Sb, then it hits the ground at the point Gb.

epsfbox{p833a.eps}

Given a list of lines segments and a list of source points, the proposed problem is to determine the corresponding falling points on the ground. To simplify the problem, it is assumed that neither horizontal lines nor crossing lines are given. Also no coincidences exist in the vertical projection of all points (the x coordinates of the end points and of the source points are all different).

Input 

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.


The input is a text file, containing several lines as follows.

The first line of the input contains the number NP (integer format) of line segments. It is followed by NP lines containing, each one, the coordinates of the two end points of a segment, in the sequence x1 y1 x2 y2, separated by single spaces. No order is supposed, for this case, between point 1 and point 2 and numbers are written in the integer format.

The next line is the number NS (integer format) of source points. It is followed by NS lines containing, each one, a pair of integer values x y, separated by a single space, which are the coordinates of the corresponding source point.

Output 

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.


NS lines of text containing, each one, the coordinate x (integer format) of the corresponding falling point G. The output values must keep the input order.

Sample Input 

1

4
14 7 3 4
11 13 16 11
1 10 6 7
2 1 4 3
3
10 4
14 14
2 13

Sample Output 

10
16
2


Note: The picture below corresponds to the sample input.

epsfbox{p833b.eps}



順著線段滑下來, 問最後的 x 軸位置

#include <stdio.h>
#define inRange(c, l, r) ((c >= l && c <= r) || (c >= r && c <= l))
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
struct seg {
    int sx, sy, ex, ey;
};
int main() {
    int t, m, n, q, i, x, y;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        seg s[100];
        for(i = 0; i < n; i++) {
            scanf("%d %d", &s[i].sx, &s[i].sy);
            scanf("%d %d", &s[i].ex, &s[i].ey);
        }
        scanf("%d", &q);
        while(q--) {
            scanf("%d %d", &x, &y);
            while(true) {
                int j = -1;
                double max = -1, ty;
                for(i = 0; i < n; i++) {
                    if(inRange(x, s[i].sx, s[i].ex)) {
                        ty = s[i].ey + (double)(s[i].sy-s[i].ey)*(x-s[i].ex)/(s[i].sx-s[i].ex);
                        if(ty < y) {
                            if(ty > max) {
                                max = ty;
                                j = i;
                            }
                        }
                    }
                }
                if(j == -1)  break;
                if((double)(s[j].sy-s[j].ey)/(s[j].sx-s[j].ex) < 0)
                    x = max(s[j].sx, s[j].ex);
                else
                    x = min(s[j].sx, s[j].ex);
                y = min(s[j].sy, s[j].ey);
            }
            printf("%d\n", x);
        }
        if(t)
            puts("");
    }
    return 0;
}


833Water Falls
台長:Morris
人氣(219) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][二分] 10566 - Crossed Ladders
此分類上一篇:[UVA][遞迴] 155 - All Squares

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文