## 10335 - Ray Inside a Polygon

Moderator: Board moderators

New poster
Posts: 9
Joined: Sat Jan 19, 2002 2:00 am

### 10335 - Ray Inside a Polygon

Well, a lot of discussions are going on about this problem. Many of you are suspicious about the correctness of the dataset. Me and Kamruzzaman, both of us have written the judge's solution for this problem. And our output didn't mismatch. Surely this is not enough to prove our correctness. But the most interesting thing behind this thing is that every input/output were hand made to ensure the correctness of the dataset. To do this, we have changed even the problem description. Initially the number of points was 1000, which finally changed to 10. So, THE DATASET IS CORRECT.
Alexander Grushetsky
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:

### 10335

For those who've got accepted for this problem.
Simulating reflections is not hard. But what is a trick with precision and rounding in this problem? When should I round current point coordinates to two digits? Only for comparing with vertexes and for output or in some other cases? Should I use usual rounding or round down? And if the result point (not during reflections) coincide with some vertex, should I output "lost forever..."?
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
When should I round current point coordinates to two digits?
I round the coordinates only for output. For the case that the ray is lost forever I check if the x-values differ by less than 0.005 and the y-values differ by less than 0.005.
Should I use usual rounding or round down?
usual rounding (printf("%.2lf")) is ok.
And if the result point (not during reflections) coincide with some vertex, should I output "lost forever..."?
yes
I checked also that the input angle for the ray points always inside the polygon, there is no case that it starts parallel to the edge it lies on. To find the edge on which the point initally is I use line intersection of original ray and check if intersection point is equal to starting point of ray (here I use an epsilon value of 1e-9).
Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

### Rounding...

I got Accepted after round down X.XX5 to X.XX
I think the main point is rounding floating-point number in this problem!!
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Isn't this a textbook example of chaotic behaviour? Very small computation errors can lead to dramatic differences in the outcome after a couple of hundered reflections or so, and that makes getting Accepted for this problem heavily dependent on the method used (I use vector calculus) and the datatypes (I use doubles), not to speak of environment dependent parameters as compiler version and processor type. Correct me if I'm wrong, but if I'm right this problem is inherently stupid. Once the judge is run on a different computer (with another math co-processor), it could become impossible to get Accepted...

Having said that, can someone check this I/O?

Code: Select all

``````4 2
2345.67 0.00 45.01
0.00 0.00
4000.00 0.00
4000.00 4000.00
-0.01 4000.00
4 6
1345.67 0.00 45.01
0.00 0.00
4000.00 0.00
4000.00 4000.00
-0.01 4000.00
4 10
1345.67 0.00 45.01
0.00 0.00
4000.00 0.00
4000.00 4000.00
-0.01 4000.00
4 100
1345.67 0.00 45.01
0.00 0.00
4000.00 0.00
4000.00 4000.00
-0.01 4000.00
4 200
1345.67 0.00 45.01
0.00 0.00
4000.00 0.00
4000.00 4000.00
-0.01 4000.00
4 999
1345.67 0.00 45.01
0.00 0.00
4000.00 0.00
4000.00 4000.00
-0.01 4000.00
4 1000
1345.67 0.00 45.01
0.00 0.00
4000.00 0.00
4000.00 4000.00
-0.01 4000.00
0 0
``````
Giving:

Code: Select all

``````-0.01 2343.69
0.00 1340.62
0.00 1337.98
4000.00 2700.24
4000.00 2695.22
3141.15 0.00
4000.00 857.00
``````
Adrian: using printf("%.2lf) would print "-0.00", is that correct?
Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
Haven't seen this as an example of chaotic behaviour, but that seems plausible.

Anyway, I get the same results as you. In my inputfile I found the following:

Code: Select all

``````4 4
2.00 0.00 0.00
0.00 0.00
4.00 0.00
4.00 4.00
0.00 4.00
4 0
2.00 0.00 45.00
0.00 0.00
4.00 0.00
4.00 4.00
0.00 4.00
4 0
2.00 0.00 63.49
0.00 0.00
4.00 0.00
4.00 4.00
0.00 4.00
4 2
2.00 0.00 40.00
0.00 0.00
4.00 0.00
4.00 4.00
0.00 4.00
3 3
1 0 91
0 0
5 5
5 0
3 10
1 0 91
0 0
5 5
5 0
3 109
1 0 134
0 0
5 5
5 0
3 11
10.99 109 0
10 10
11 110
11 10
3 501
10.99 109 0
10 10
11 110
11 10
0 0``````
Giving

Code: Select all

``````lost forever...
4.00 2.00
lost forever...
0.00 2.97
0.83 0.00
0.48 0.48
5.00 2.35
10.99 108.99
10.97 106.83
``````
Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
Oh, and I use

Code: Select all

``````  if (p.x < 0 && fabs(p.x) < 0.005) p.x = -p.x;
if (p.y < 0 && fabs(p.y) < 0.005) p.y = -p.y;``````
to make sure that I don't print "-0.00", though I'm not sure if it's necessary (don't ask me why I use -p.x rather than 0, because I have no idea ).
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Same results...
Made the change you suggested, but still WA.
Could you please run one more test file?

Code: Select all

``````8 0
34.41 0.48 123.45
10.56 26.42
15.08 4.96
29.66 0.78
39.16 0.18
46.81 16.13
43.00 28.70
30.11 35.08
21.55 30.12
8 1
34.41 0.48 123.45
10.56 26.42
15.08 4.96
29.66 0.78
39.16 0.18
46.81 16.13
43.00 28.70
30.11 35.08
21.55 30.12
8 10
34.41 0.48 123.45
10.56 26.42
15.08 4.96
29.66 0.78
39.16 0.18
46.81 16.13
43.00 28.70
30.11 35.08
21.55 30.12
8 100
34.41 0.48 123.45
10.56 26.42
15.08 4.96
29.66 0.78
39.16 0.18
46.81 16.13
43.00 28.70
30.11 35.08
21.55 30.12
8 1000
34.41 0.48 123.45
10.56 26.42
15.08 4.96
29.66 0.78
39.16 0.18
46.81 16.13
43.00 28.70
30.11 35.08
21.55 30.12
0 0
``````
(Hope it's convex, looks like it on my sketch)

Code: Select all

``````16.05 28.27
17.63 4.23
11.94 19.86
27.28 33.44
39.49 0.87
``````
Hope you get something completely different...
Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
I get the same results.
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

### Re: About 10335 - Ray inside the polygon

Md. Sajjad Hossain wrote:But the most interesting thing behind this thing is that every input/output were hand made to ensure the correctness of the dataset.
[EDIT: SORRY I MADE A MISTAKE, SEE MY NEXT POSTING]

Thanks for so many spoiled hours (56 Accept out of 872 submissions to date).
Last edited by little joey on Tue Oct 12, 2004 5:52 pm, edited 1 time in total.
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Thanks for the help, got AC now. The input contains dirty cases (see my other posting).
Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
Hmm, are you sure about that?

My solution crashes on this input (it gets angry since it cannot determine the initial line segment).
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
So now I made a mistake
Case 27 is

Code: Select all

``````3 0
7.00 2.50 0.00
2.00 1.00
12.00 4.00
3.00 7.00``````
The initial point lies on an edge, but the ray points outside the triangle, and you have to go backward to hit (2.25, 2.50), the accepted answer.

Here is part of my code that gets accepted[c] cases=0;
while(scanf("%d%d",&points,&reflections)==2){
if(!points) break;
scanf("%lf%lf%lf",&oldx,&oldy,&oldalpha);
oldalpha*=pi/180.0;
for(i=0;i<points;i++){
scanf("%lf%lf",&x,&y);
}
if(++cases==27){
assert(points==3);
assert(reflections==0);
assert(oldx==7.00);
assert(oldy==2.50);
assert(oldalpha==0.00);
assert(x[0]==2.00);
assert(y[0]==1.00);
assert(x[1]==12.00);
assert(y[1]==4.00);
assert(x[2]==3.00);
assert(y[2]==7.00);
}
[/c]
Sorry for the previous mistake, but brute forcing is a hand job
Still my point remains that the input is dirty.