10907  Art Gallery
Moderator: Board moderators
10907  Art Gallery
Can I assume the followings?
1. There is excatly one vertex which produces an angle strictly greater than 180 degrees.
2. N >= 4.
And any test case?
1. There is excatly one vertex which produces an angle strictly greater than 180 degrees.
2. N >= 4.
And any test case?

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Yes, to both your questions.
It's not much, but I used these to test my solution
It's not much, but I used these to test my solution
Code: Select all
7
0 5
5 0
10 7
15 0
20 5
15 10
5 10
7
0 5
5 0
10 7
15 0
20 5
15 10
5 10
Code: Select all
Gallery #1
71.67
60.71
115.00
60.71
71.67
100.00
100.00
A bit tricky case:
The output should be:
Code: Select all
5
0 0
50 50
100 0
100 100
0 100
6
0 0
60 40
40 40
40 60
60 60
50 50
Code: Select all
Gallery #1
5000.00
5000.00
5000.00
7500.00
7500.00
7500.00
hmm.. I passed both test cases.
Just created some here: 10907.zip or 10907.tar.gz
There are 1000 random cases and 2 handmade.
Hope your output are different from mine.
Just created some here: 10907.zip or 10907.tar.gz
There are 1000 random cases and 2 handmade.
Hope your output are different from mine.
I'm getting WA, too, and my solution does pass both cases above. On some of your random cases my solution's output differs from yours, I'm going to check some of it by hand when I have the time.Cho wrote:hmm.. I passed both test cases.
Just created some here: 10907.zip or 10907.tar.gz
There are 1000 random cases and 2 handmade.
Hope your output are different from mine.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
The output from my accepted program is here http://home.hccnet.nl/pj.wulff/cho10907.out
Your input file contains clockwise polygons, which my program doesn't treat well; it's given that all polygons are anticlockwise, and my program assumes that without checking.
There are quite a few differences between your file and mine; some of them are rounding errors, some are plain wrong, and your output for some cases is quite odd (see f.i. gallery 27 in your output).
Happy hunting!
Your input file contains clockwise polygons, which my program doesn't treat well; it's given that all polygons are anticlockwise, and my program assumes that without checking.
There are quite a few differences between your file and mine; some of them are rounding errors, some are plain wrong, and your output for some cases is quite odd (see f.i. gallery 27 in your output).
Happy hunting!
I found my bug, AC nowmisof wrote:I'm getting WA, too, and my solution does pass both cases above. On some of your random cases my solution's output differs from yours, I'm going to check some of it by hand when I have the time.Cho wrote:hmm.. I passed both test cases.
Just created some here: 10907.zip or 10907.tar.gz
There are 1000 random cases and 2 handmade.
Hope your output are different from mine.
Just for the reference, my fixed output for your input is here: (probably it doesn't differ from little joey's, but I'm too lazy to check )
http://people.ksp.sk/~misof/junk/10907.mf.out
a trouble
hi. i have a trouble.
in my program,
i have a function is_visible(point P),
which returns wheter P is visible from LIGHT.
at first, i thought it will return true if there are no intersecting line segments,
but in this tricky case it wouldn't be.
supposing LIGHT is on (0, 0) and P(100, 0),
is_visible(P) must be FALSE,
but my buggedfunction returns TRUE,
for there is no intersecting line between them.
how can I detect this case?
is there no way except checking whether a point is inside the polygon?
....
the polygon above is as mf's data.5
0 0
50 50
100 0
100 100
0 100
in my program,
i have a function is_visible(point P),
which returns wheter P is visible from LIGHT.
at first, i thought it will return true if there are no intersecting line segments,
but in this tricky case it wouldn't be.
supposing LIGHT is on (0, 0) and P(100, 0),
is_visible(P) must be FALSE,
but my buggedfunction returns TRUE,
for there is no intersecting line between them.
how can I detect this case?
is there no way except checking whether a point is inside the polygon?
....
Sorry For My Poor English..

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Imagine two lines, one that runs through the point before the concave point and the concave point, and another that runs through the concave point and the point after the concave point. In the example you give these points are before: (0,0), concave: (50,50) and after: (100,0). Now a point is only unlit if the light source is strictly to the right of one of these lines, and the point is strictly to the right of the other line. In all other cases the point is lit (or outside the polygon).
The formula to determine if a point is stricktly to the right of a line is well known.
For the example you give, the light source (0,0) is strictly to the right of the second line ((50,50)  (100,0)) and the point (100,0) is strictly to the right of the first line ((0,0)  (50,50)), so the point is unlit.
The formula to determine if a point is stricktly to the right of a line is well known.
For the example you give, the light source (0,0) is strictly to the right of the second line ((50,50)  (100,0)) and the point (100,0) is strictly to the right of the first line ((0,0)  (50,50)), so the point is unlit.
2 misof:
My program gives output similar to yours one, but
I get WA over and over again
Can you explain why your answer in Gallery 4 light 11
is 130.12 ? I believe real answer is 130.125000, so
my program outputs 130.13. Also interesting that your answer
to Gallery 4 light 13 is 129.38! Real answer is 129.375000
and here your program rounds it to +infinity ?!
P.S.
BTW, obiously that judge accepts programs that give different
answers to the same test. Is it about to be changed?
My program gives output similar to yours one, but
I get WA over and over again
Can you explain why your answer in Gallery 4 light 11
is 130.12 ? I believe real answer is 130.125000, so
my program outputs 130.13. Also interesting that your answer
to Gallery 4 light 13 is 129.38! Real answer is 129.375000
and here your program rounds it to +infinity ?!
P.S.
BTW, obiously that judge accepts programs that give different
answers to the same test. Is it about to be changed?
My code output 130.13. I've compared the output of Littlejoey's, misof's and mine. There are numerous differences between any pair of us although we all got AC. I think we are all lucky to produce output which matches with judge's solution.kp wrote:Can you explain why your answer in Gallery 4 light 11
is 130.12 ? I believe real answer is 130.125000
I round the answers using standard routines ("%.2f"). In the case when the answer can be represented in a double in an exact way and the .5case occurs (i.e., the value that has to be rounded is exactly between two possible outputs), the "more round", i.e., even output is chosen. That's why 130.125 gets rounded to 130.120, but 192.375 to 192.38.kp wrote:2 misof:
My program gives output similar to yours one, but
I get WA over and over again
Can you explain why your answer in Gallery 4 light 11
is 130.12 ? I believe real answer is 130.125000, so
my program outputs 130.13. Also interesting that your answer
to Gallery 4 light 13 is 129.38! Real answer is 129.375000
and here your program rounds it to +infinity ?!
P.S.
BTW, obiously that judge accepts programs that give different
answers to the same test. Is it about to be changed?
About the judge: Isn't it just the case that they have a special judge that allows some precision errors? Why should this change?
About possible bugs: The bug I made and didn't find during the contest was that my code for intersecting a polygon and a halfplane worked too good I.e.,
Code: Select all
++
 
 
++ 
 
++
Code: Select all
++
 
 
++

+