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

Post by Giorgi » 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.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Aug 12, 2006 7:17 pm

That's a correct algorithm.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » 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.

rammestain
New poster
Posts: 18
Joined: Fri Apr 21, 2006 11:34 am

Post by rammestain » 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! :(

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » 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
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:

Post by mf » 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.

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ » Fri Aug 18, 2006 7:27 am

I still got WA :(
Some I/O please?

Arktus
New poster
Posts: 3
Joined: Mon Nov 22, 2004 5:26 pm
Location: Tehran

Post by Arktus » 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.
Arktus

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

Post by StatujaLeha » 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.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » 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.)

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » 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.
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

Post by StatujaLeha » 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.

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

WA, Need some testcases

Post by Ecou » 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>
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

Post by StatujaLeha » 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

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

Those all pass.

Post by Ecou » 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? :)

Post Reply

Return to “Volume 110 (11000-11099)”