OJ Board

Posted: **Sat Aug 12, 2006 6:59 pm**

Is this algorthm true?
I make convex hull with this points. Then if given point is inside polygon then it will be in one triangle.

Posted: **Sat Aug 12, 2006 7:17 pm**

That's a correct algorithm.

Posted: **Sat Aug 12, 2006 7:28 pm**

This one sent me to bed last night...

I just tried it - I can't even read the points in 10 secs in Java.

Posted: **Sun Aug 13, 2006 7:26 am**

I use a similar algorithm:
first I find convex hull with O(nlgn) and then see if the point is inside the polygon or not with O(n).
but this give me TLE!

Posted: **Sun Aug 13, 2006 7:36 am**

the first set may have 100000 points, but is that also for second set? if the second set also have so many points, it should be tle using the convex hull algorithm above

Posted: **Sun Aug 13, 2006 7:43 am**

then see if the point is inside the polygon or not with O(n).

You can do that in O(log n) time using binary search. Convex hull is a convex polygon, think about it.

Posted: **Fri Aug 18, 2006 7:27 am**

I still got WA

Some I/O please?

Posted: **Sat Aug 19, 2006 8:55 am**

The size of the second set is about 400000.
I read them all first, and after that I find the convex hull, and then sort the convex point with the second set (by their angle to the convex base point )
and with a traverse on them I find the two nearest convex points around each point of the second set, and then I use the left turn check for finding the state of that point, this is about O(n*log(n)). but I am getting wrong answer.

Posted: **Sun Aug 27, 2006 11:50 am**

What algorithm did you use to make convex hull? I used Graham's scan, but it too slow.

Posted: **Sun Aug 27, 2006 8:57 pm**

StatujaLeha wrote:What algorithm did you use to make convex hull? I used Graham's scan, but it too slow.

I always use Monotone Chain Convex Hull algorithm. It's quite quick. (Note, that you can use cross product to check if three points create a clockwise or a counter-clockwise turn and so there is no need to use float arithmetics.)

Posted: **Sun Aug 27, 2006 11:00 pm**

StatujaLeha wrote:What algorithm did you use to make convex hull? I used Graham's scan, but it too slow.

Funny you say so - I used Graham's scan too.

Posted: **Mon Aug 28, 2006 10:12 am**

Martin Macko wrote:
StatujaLeha wrote:What algorithm did you use to make convex hull? I used Graham's scan, but it too slow.
(Note, that you can use cross product to check if three points create a clockwise or a counter-clockwise turn and so there is no need to use float arithmetics.)

If you use float arithmetic to check it you will get WA in this problem.

Funny you say so - I used Graham's scan too.

I said not exactly: I had in mind that my solution is too slow.

Posted: **Fri Sep 01, 2006 2:09 am**

I get WA, and i can't find a testcase where output isn't what i expect,
so looking for bugs/critical input.

Code: Select all

<removed, resolved>

Posted: **Fri Sep 01, 2006 1:02 pm**

Input:

10
0 0
4 0
0 4
4 4
1 1
2 2
2 2
3 2
2 3
3 3
25
0 0
0 1
0 2
0 3
0 4
1 0
1 1
1 2
1 3
1 4
2 0
2 1
2 2
2 3
2 4
3 0
3 1
3 2
3 3
3 4
4 0
4 1
4 2
4 3
4 4

10
0 0
4 0
0 4
4 4
1 1
2 2
2 2
3 2
2 3
3 3
22
-1 -1
-1 0
-1 1
-1 2
-1 3
-1 4
-1 5
-1 1
5 1
-1 2
5 2
-1 3
5 3
-1 4
5 4
-1 5
0 5
1 5
2 5
3 5
4 5
5 5

8
0 0
4 0
0 4
4 4
5 2
-1 2
2 3
2 2
27
0 0
0 1
0 2
0 3
0 4
1 0
1 1
1 2
1 3
1 4
2 0
2 1
2 2
2 3
2 4
3 0
3 1
3 2
3 3
3 4
4 0
4 1
4 2
4 3
4 4
-1 2
5 2

8
0 0
4 0
0 4
4 4
5 2
-1 2
2 3
2 2
36
-2 -1
-2 0
-2 1
-2 2
-2 3
-2 4
-2 5
-1 -1
-1 0
-1 1
-1 3
-1 4
-1 5
0 -1
0 5
1 -1
1 5
2 -1
2 5
3 -1
3 5
4 -1
4 5
5 -1
5 0
5 1
5 3
5 4
5 5
6 -1
6 0
6 1
6 2
6 3
6 4
6 5

10
0 0
-1 2
2 5
2 -1
4 4
5 2
2 3
4 0
0 4
2 2
29
0 0
0 1
0 2
0 3
0 4
1 0
1 1
1 2
1 3
1 4
2 -1
2 0
2 1
2 2
2 3
2 4
2 5
3 0
3 1
3 2
3 3
3 4
4 0
4 1
4 2
4 3
4 4
-1 2
5 2

10
5 2
-1 2
2 5
2 -1
2 3
0 4
4 4
0 0
2 2
4 0
52
-2 -2
-2 -1
-2 0
-2 1
-2 2
-2 3
-2 4
-2 5
-2 6
-1 -2
-1 -1
-1 0
-1 1
-1 3
-1 4
-1 5
-1 6
0 -2
0 -1
0 5
0 6
1 -2
1 -1
1 5
1 6
2 -2
2 6
3 -2
3 -1
3 5
3 5
4 -2
4 -1
4 5
4 6
5 -2
5 -1
5 0
5 1
5 3
5 4
5 5
5 6
6 -2
6 -1
6 0
6 1
6 2
6 3
6 4
6 5
6 6

Output:

inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
inside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside
outside

Posted: **Fri Sep 01, 2006 2:24 pm**

You have a double point (2,2) in the first testcases for set1. if i remove
that i get the exact same output. Got any more?

OJ Board

11072 - Points

11072 - Points

WA, Need some testcases

Those all pass.