3529 - D. 降水问题
在一个竖直的平面中，钉着若干条木块，木块不会相交或相接。有一滴水往下落，如果水从s处的落下，那么它将会落到哪一点上？如下图，如果水从Sb开始下降，那么，他将落到Gb点，如果它从Sa处落下，他将落到Ga点。
<br />
现在，给定若干木板以及若干水滴的描述，对每一个水滴，求出它会落到<span>X</span>轴上的哪一点。<span></span>
约定，如下面的图，雨水的路线如下线条所示：<span></span>
<br />
<br />
并且，不会有一块水平或者竖直的木板。
<br />
Input
第一行有一个正整数n（1≤n≤100），表示木板的条数。以下n行，每一行有4个正整数x1,y1,x2,y2，表示一条连接（x1,y1）与（x2,y2）的木板（1≤x1,y1,x2,y2≤1000）。下面的一行有一个正整数m，表示雨滴的数目(1≤m≤20)。以下m行，每一行有两个正整数，表示雨滴的横坐标与纵坐标(都小于等于1000)。
Output
m行，每一行一个正整数，表示对应的雨滴落地时的横坐标。
Examples
Input
4 14 7 3 4 11 13 16 11 1 10 6 7 2 1 4 3 3 10 4 14 14 2 1
Output
10 16 2
Solution C++
#include <iostream> using namespace std; #define MAXN 100 struct TSegment { double x1, y1, x2, y2; double a, b, c; bool del; } s[MAXN]; int n, m; int res(double x, double y) { for (int i = 0; i < n; i++) s[i].del = 0; while (1) { double ymax = 0; int _k; for (int k = 0; k < n; k++) if (!s[k].del && (x - s[k].x1) * (s[k].x2 - x) >= 0) { double y0 = (-s[k].c - s[k].a * x) / s[k].b; if (y0 <= y && y0 >= ymax) ymax = y0, _k = k; } if (ymax == 0) break; if (s[_k].y1 <= s[_k].y2) x = s[_k].x1, y = s[_k].y1; else x = s[_k].x2, y = s[_k].y2; s[_k].del = 1; } return (int)x; } int main() { while (cin >> n) { //cin >> n; for (int i = 0; i < n; i++) { cin >> s[i].x1 >> s[i].y1 >> s[i].x2 >> s[i].y2; s[i].a = s[i].y2 - s[i].y1; s[i].b = s[i].x1 - s[i].x2; s[i].c = s[i].x2 * s[i].y1 - s[i].x1 * s[i].y2; } cin >> m; for (int i = 0; i < m; i++) { double x, y; cin >> x >> y; cout << res(x, y) << endl; } } return 0; }