### 833 - Water Falls

Posted:

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

I always get wrong answer. [/cpp]

I always get wrong answer. [/cpp]

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=21&t=42123

Page **1** of **1**

Posted: **Mon Nov 11, 2002 6:18 am**

Does anyone have some test cases for prolem 833 (Water Falls) ?

I always get wrong answer. [/cpp]

I always get wrong answer. [/cpp]

Posted: **Thu Jun 17, 2004 6:47 pm**

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

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**

?, the problem statement clearly says**jagadish** won't be valid i think.

a test case to try
output is:
One problem would be ( but not surely) floating point/precision error... my approach is totally on Integers calculations. Just a thought.

so the input suggested byAlso 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).

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
```

Code: Select all

```
1
1
10
10
10
10
13
8
```

Posted: **Mon Jun 09, 2008 8:43 am**

I found the weakness of current datasets.

In this case: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++:

In this case:

Code: Select all

```
1
2
1 4 5 1
3 3 6 2
1
4 4
```

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

Posted: **Tue Nov 18, 2008 1:22 pm**

There is no worry about the precision of floating point. My program stores all data with double format and works really fine.the LA-Z-BOy wrote:?, the problem statement clearly saysAlso 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 byjagadishwon't be valid i think.

a test case to tryoutput is: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`

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.

Posted: **Mon Aug 22, 2011 12:50 am**

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

sample input:

1

2 13

3

1 10 6 7

6 4 10 5

10 1 6 2