10907 - Art Gallery

[Cho]

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?

[little joey]

Yes, to both your questions.

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

[mf]

A bit tricky case:

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

The output should be:

Code: Select all

Gallery #1
5000.00
5000.00
5000.00
7500.00
7500.00
7500.00

[Cho]

hmm.. I passed both test cases.
Just created some here: 10907.zip or 10907.tar.gz
There are 1000 random cases and 2 hand-made.
Hope your output are different from mine.

[misof]

hmm.. I passed both test cases.
Just created some here: 10907.zip or 10907.tar.gz
There are 1000 random cases and 2 hand-made.
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.

[little joey]

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 anti-clockwise, 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!

[misof]

hmm.. I passed both test cases.
Just created some here: 10907.zip or 10907.tar.gz
There are 1000 random cases and 2 hand-made.
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.

I found my bug, AC now

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

[wook]

hi. i have a trouble.

5
0 0
50 50
100 0
100 100
0 100

the polygon above is as mf's data.


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 bugged-function 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?

....

[little joey]

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.

[Cho]

Thx, little joey and misof. Just mixed my mistake.
Btw, I intended to generate anti-clockwise polygons. I think there should be no problem in my input. There are still atmost uncountable precise error between my output and you guy's output, but I can also get AC.

[kp]

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?

[Cho]

Can you explain why your answer in Gallery 4 light 11
is 130.12 ? I believe real answer is 130.125000

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.

[misof]

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?

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 .5-case 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.

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

+----+
|    |
|    |
+--+ |
   | |
   +-+ 

intersected by the halfplane x<=3 is

Code: Select all

+--+
|  |
|  |
+--+
   |
   + 

I.e., also the bottommost point belongs in the intersection. While this is correct, when I later checked in which part of the polygon a point lies, for some of them I got a wrong result, because the bottommost line segment shouldn't belong to the topmost part. Maybe this will help someone

[kp]

I see...

Does anybody know how to use
such routines as printf("%.2f") in PASCAL?

I believe Format() is restricted ?!

[misof]

I see...

Does anybody know how to use
such routines as printf("%.2f") in PASCAL?

I believe Format() is restricted ?!

var x : double;
x := 1.2345;
writeln(x:0:2); { 0 is the total # of chars (if non-zero, aligns right), 2 is the # of decimal places }