## 10907 - Art Gallery

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

Moderator: Board moderators

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

### 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?

little joey
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

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
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 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
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 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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
misof wrote:
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 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
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

### a trouble

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?

....
Sorry For My Poor English..

little joey
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.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
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
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
kp wrote: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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
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?
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
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
I see...

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

I believe Format() is restricted ?!

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
kp wrote: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 }