11072 - Points

[Giorgi]

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.

[mf]

That's a correct algorithm.

[Darko]

This one sent me to bed last night...

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

[rammestain]

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!

[ayon]

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

[mf]

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.

[FAQ]

I still got WA
Some I/O please?

[Arktus]

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.

[StatujaLeha]

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

[Martin Macko]

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

[Krzysztof Duleba]

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.

[StatujaLeha]

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.

[Ecou]

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>

[StatujaLeha]

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

[Ecou]

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?