游客 注册 | 登录
中文 | En

3529 - D. 降水问题

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

在一个竖直的平面中，钉着若干条木块，木块不会相交或相接。有一滴水往下落，如果水从s处的落下，那么它将会落到哪一点上？如下图，如果水从Sb开始下降，那么，他将落到Gb点，如果它从Sa处落下，他将落到Ga点。 

<br />


现在，给定若干木板以及若干水滴的描述，对每一个水滴，求出它会落到<span>X</span>轴上的哪一点。<span></span> 


约定，如下面的图，雨水的路线如下线条所示：<span></span> 


<br />


<br />


并且，不会有一块水平或者竖直的木板。


<br />

题目输入

第一行有一个正整数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)。

题目输出

m行，每一行一个正整数，表示对应的雨滴落地时的横坐标。

输入/输出样例

输入格式

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

输出格式

10
16
2

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;
}

Java解答

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			int num = in.nextInt();
			int[][] arr = new int[num][4];
			for (int i = 0; i < num; i++)
				for (int j = 0; j < 4; j++)
					arr[i][j] = in.nextInt();
			int rain = in.nextInt();
			int[][] rainArr = new int[rain][2];
			for (int i = 0; i < rain; i++)
				for (int j = 0; j < 2; j++)
					rainArr[i][j] = in.nextInt();
			boolean[] visited = new boolean[num];
			double[] k = new double[num];
			double[] b = new double[num];
			for (int i = 0; i < num; i++) {
				k[i] = (arr[i][3] - arr[i][1]) * 1.0 / (arr[i][2] - arr[i][0]);
				b[i] = arr[i][1] - k[i] * arr[i][0];
			}
			for (int i = 0; i < rain; i++) {
				for (int j = 0; j < num; j++) {
					visited[j] = false;
				}
				int currentX = rainArr[i][0];
				double currentY = rainArr[i][1];
				for (int jj = 0; jj < num; jj++) {
					double testY, maxY = -1;
					int currentNum = -1, lowYIndex = -1;
					for (int j = 0; j < num; j++) {
						if (!visited[j]) {
							testY = k[j] * currentX + b[j];
							if ((testY <= currentY && testY > maxY)&& ((currentX >= arr[j][0] && currentX <= arr[j][2]) || (currentX <= arr[j][0] && currentX >= arr[j][2]))) {
								maxY = testY;
								currentNum = j;
								if (arr[j][1] < arr[j][3])
									lowYIndex = 1;
								else
									lowYIndex = 3;
							}
							
						}
					}
					if (-1 == currentNum) {
						break;
					}
					visited[currentNum] = true;
					currentX = arr[currentNum][lowYIndex - 1];
					currentY = arr[currentNum][lowYIndex];
				}
				System.out.println(currentX);
			}
		}
	}
}
请先登陆