Page 2 of 2
Posted: Fri Nov 11, 2005 7:06 pm
by ayon
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.
Re: 10078 tests
Posted: Thu Jan 12, 2006 6:22 am
by eg_frx
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?
Posted: Thu Jan 12, 2006 6:34 am
by helloneo
my AC code make same outputs..
Posted: Fri Jan 13, 2006 5:02 am
by eg_frx
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.
Re: 10078 - The Art Gallery
Posted: Wed Jul 02, 2008 10:20 pm
by Robert Gerbicz
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].
Re: 10078 - The Art Gallery
Posted: Mon Mar 29, 2010 6:37 am
by jiunyao
This problem can be solve by finding convex hull. My AC program uses convex-hull algorithm and it performs well.