10078 - The Art Gallery

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

Moderator: Board moderators

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Fri Nov 11, 2005 7:06 pm

thats right mf, i also noticed that lately, i missed checking the 2nd point and got wa, after checking that point i got accepted. anyhow, the judge doesn't give such critical inputs(as tan_yui said, closed area inside the whole area). so checking cw/ccw or convex hull, both can solve the problem. thanks to mf and tan_Yui for their good reply.
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

eg_frx
New poster
Posts: 21
Joined: Sat Oct 02, 2004 2:17 pm

Re: 10078 tests

Post by eg_frx » Thu Jan 12, 2006 6:22 am

diac_paul wrote:Can anyone give me some data tests so I can find my mistake? For exemple what should be the output for this test:
7
3 0
6 1
7 5
5 8
3 8
2 7
2 6
8
3 0
6 1
7 5
5 8
3 8
2 7
2 6
1 5
6
3 1
5 6
4 6
3 7
2 6
1 6
5
1 1
1 5
3 5
6 7
9 5
3
1 1
2 2
2 0
4
0 0
0 1000
500 501
1000 0
4
0 0
0 1000
500 499
1000 0
0
?
I get "No Yes Yes Yes No No Yes" ( ofcourse, with breaklines ).
Is this correct? I think it's rigth. Does anybody knows some other tricky tests?
I got the same answers, and I got WA.

Since the problem says the co-ordinates are given in order, I can safely assume the polygon is a simple polygon, can't I?

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Thu Jan 12, 2006 6:34 am

my AC code make same outputs..

eg_frx
New poster
Posts: 21
Joined: Sat Oct 02, 2004 2:17 pm

Post by eg_frx » Fri Jan 13, 2006 5:02 am

Found the trick.

Try the following input and see if you get it right

4
1 1
0 0
1 2
2 0
0

See the trick? (Well, at least this is the case i missed.)

Still, thanks for sharing helloneo. :D

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 10078 - The Art Gallery

Post by Robert Gerbicz » Wed Jul 02, 2008 10:20 pm

This problem is NOT a convex hull finding task. The points are sorted, as described in the problem statement.
[my AC solution haven't used a convex hull algorithm].

jiunyao
New poster
Posts: 2
Joined: Wed Feb 24, 2010 2:33 pm

Re: 10078 - The Art Gallery

Post by jiunyao » Mon Mar 29, 2010 6:37 am

This problem can be solve by finding convex hull. My AC program uses convex-hull algorithm and it performs well.

Post Reply

Return to “Volume 100 (10000-10099)”