10335 - Ray Inside a Polygon

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Md. Sajjad Hossain
New poster
Posts: 9
Joined: Sat Jan 19, 2002 2:00 am
Location: Bangladesh

10335 - Ray Inside a Polygon

Post by 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
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:

10335

Post by 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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by 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
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Rounding...

Post by 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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by 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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by 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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by 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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by 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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

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

Post by little joey »

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

Post by little joey »

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

Post by 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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

So now I made a mistake :oops:
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 :wink:
Still my point remains that the input is dirty.
Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by 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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

I just did that.
Post Reply

Return to “Volume 103 (10300-10399)”