10078 - The Art Gallery

[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.

[eg_frx]

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]

my AC code make same outputs..

[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.

[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].

[jiunyao]

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