10335 - Ray Inside a Polygon

[Md. Sajjad Hossain]

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]

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..."?

[Adrian Kuegel]

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]

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]

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]

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]

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]

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]

I get the same results.

[little joey]

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).

[little joey]

Thanks for the help, got AC now. The input contains dirty cases (see my other posting).

[Per]

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]

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.

[Adrian Kuegel]

Did you already write an email to the admins? I think this test case should be removed.
It seems I was among the lucky people who got accepted by assuming the ray points inside, and handled it like a line instead (thus in this case it goes "backwards").

[little joey]

I just did that.