## 11072 - Points

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

Moderator: Board moderators

Giorgi
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

### 11072 - Points

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
That's a correct algorithm.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
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
New poster
Posts: 18
Joined: Fri Apr 21, 2006 11:34 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!

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh
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
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm
I still got WA

Arktus
New poster
Posts: 3
Joined: Mon Nov 22, 2004 5:26 pm
Location: Tehran
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.
Arktus

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
What algorithm did you use to make convex hull? I used Graham's scan, but it too slow.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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.)

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
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.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
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.

Ecou
New poster
Posts: 10
Joined: Wed Aug 09, 2006 11:47 pm

### WA, Need some testcases

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>
``````
Last edited by Ecou on Fri Sep 01, 2006 4:14 pm, edited 1 time in total.

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
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
New poster
Posts: 10
Joined: Wed Aug 09, 2006 11:47 pm

### Those all pass.

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?