Page 1 of 1

833 - Water Falls

Posted: Mon Nov 11, 2002 6:18 am
by david_ciang
Does anyone have some test cases for prolem 833 (Water Falls) ?

I always get wrong answer. :( [/cpp]

Posted: Thu Jun 17, 2004 6:47 pm
by jagadish
i guess the only critical input is when endpoints of lines have same x co-ordinate

sample input:

1
2 13
3
1 10 6 7
6 4 10 5
10 1 6 2

Posted: Mon Aug 23, 2004 9:56 am
by the LA-Z-BOy
?, the problem statement clearly says
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).
so the input suggested by jagadish won't be valid i think.
a test case to try

Code: Select all

1

8
10 12 1 3
4 8 6 10
2 5 7 10
12 11 16 9
13 8 15 9
10 5 18 8
13 5 16 6
8 3 4 5
8
5 13
6 13
15 12
14 9
12 7
15 8
14 6
7 4
output is:

Code: Select all

1
1
10
10
10
10
13
8
One problem would be ( but not surely) floating point/precision error... my approach is totally on Integers calculations. Just a thought. :)

833 - Water Falls

Posted: Mon Jun 09, 2008 8:43 am
by DJWS
I found the weakness of current datasets.

In this case:

Code: Select all

1

2
1 4 5 1
3 3 6 2
1
4 4
The answer should be 6, not 5.
However my accepted code outputs 5.

In my code, I sort all segments by their maximal height.
And then determine if the source flows onto the segments in the sorted sequence.
This algorithm is not correct in the above case.
But It is judged as Accepted.

Here is my accepted code, written in C++:

Code: Select all

#include <iostream>
#include <algorithm>
using namespace std;

	int N, M;

struct Segment {
	int x1, y1, x2, y2, minx, maxx;
	
	void refresh() {
		if (y1 > y2) {
			swap(x1, x2);
			swap(y1, y2);
		}
		minx = min(x1, x2);
		maxx = max(x1, x2);
	}
	
	friend istream& operator>>(istream& in, Segment& s) {
		return in >> s.x1 >> s.y1 >> s.x2 >> s.y2;
	}
	
	bool operator<(const Segment& s) const {
		return y2 > s.y2;
	}
} S[100];

int main() {
	int cs; cin >> cs;
	while (cs--) {
		cin >> N;
		for (int i=0; i<N; ++i) {
			cin >> S[i];
			S[i].refresh();
		}
		sort(S, S+N);

		cin >> M;
		while (M--) {
			int x, y;
			cin >> x >> y;
			for (int i=0; i<N; ++i)
				if (y > S[i].y1 && S[i].minx <= x && x <= S[i].maxx) {
					x = S[i].x1;
					y = S[i].y1;
				}

			cout << x << endl;
		}
		if (cs) cout << endl;
	}
	return 0;
}

Re: 833 - Water Falls

Posted: Tue Nov 18, 2008 1:22 pm
by DD
the LA-Z-BOy wrote:?, the problem statement clearly says
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).

so the input suggested by jagadish won't be valid i think.
a test case to try

Code: Select all

1

8
10 12 1 3
4 8 6 10
2 5 7 10
12 11 16 9
13 8 15 9
10 5 18 8
13 5 16 6
8 3 4 5
8
5 13
6 13
15 12
14 9
12 7
15 8
14 6
7 4
output is:

Code: Select all

1
1
10
10
10
10
13
8

One problem would be ( but not surely) floating point/precision error... my approach is totally on Integers calculations. Just a thought. :)
There is no worry about the precision of floating point. My program stores all data with double format and works really fine.

Re: 833 - Water Falls

Posted: Mon Aug 22, 2011 12:50 am
by x3xd
i guess the only critical input is when endpoints of lines have same x co-ordinate

sample input:

1
2 13
3
1 10 6 7
6 4 10 5
10 1 6 2