11122 - Tri Tri

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

Moderator: Board moderators

kalinov
New poster
Posts: 27
Joined: Tue Mar 29, 2005 3:10 pm
Location: Croatia

Post by kalinov »

david wrote:Anyway here's my code, in case someone wants to test it.
Your program fails on this case:

Code: Select all

input:
1

0 0 5 0 2 4
4 0 6 0 -4 16

output:
pair 1: yes

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

Post by fpavetic »

kalinov wrote:
david wrote:Anyway here's my code, in case someone wants to test it.
Your program fails on this case:

Code: Select all

input:
1

0 0 5 0 2 4
4 0 6 0 -4 16

output:
pair 1: yes
hvala :)

and here is one more test case that helped me:

1

0 1 2 0 3 1
1 3 2 0 3 3

output:

pair 1: yes

cpphamza
New poster
Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm

Re: 11122 - Tri Tri

Post by cpphamza »

I'm a bit confused about this problem, does interior point means a lattice point or just an a common area? I assume the first, so shouldn't this testcase output no (I see that you output yes for it)?

0 0 1 0 1 1
0 0 1 0 1 1

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

Post by Darko »

Those two have all their points in common - I am not sure why you thought that we were looking for points with integer coordinates only.

I liked this problem - especially because I learned about this (although it might be "common sense" for some):
http://en.wikipedia.org/wiki/Separating_axis_theorem

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

I have code to find intersection of 2 convex polygons, so I just used that, then compute the area of the resulting polygons.

cpphamza
New poster
Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm

Post by cpphamza »

Darko wrote:Those two have all their points in common - I am not sure why you thought that we were looking for points with integer coordinates only.
I thought so because in the sample input we have:
0 0 2 0 0 2
1 1 3 3 2 3
and answer is no although they've a common area (infinite non integer points)! can you please explain that?

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo »

cpphamza wrote:
Darko wrote:Those two have all their points in common - I am not sure why you thought that we were looking for points with integer coordinates only.
I thought so because in the sample input we have:
0 0 2 0 0 2
1 1 3 3 2 3
and answer is no although they've a common area (infinite non integer points)! can you please explain that?
No, there isn't any common point..
A point of a triangle is on the edge of the other triangle..
It is not considered as a common point by the problem statement

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

another way to say it is that the answer is "yes" iff the intersection of the two triangles have positive area. A set of infinite number of points, even if there are uncountable number of points need not have positive area (measure)

cpphamza
New poster
Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm

Post by cpphamza »

I have code to find intersection of 2 convex polygons, so I just used that, then compute the area of the resulting polygons.
I'm interested in implementing a convex polygon intersection algorithm, can you post your algorithm? (code, resources, links ...)

Also can anyone expalin other approaches to solve this problem?
Thanks.

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

Post by Darko »

I projected triangles onto 6 lines (normal to each side) and looked for gaps. It works for any two convex polygons - it's from that theorem (you can separate two polygons if there is a gap in projection - separating axis could go through that gap, normal to the line).

rcrezende
New poster
Posts: 7
Joined: Mon Nov 28, 2005 4:53 am

Post by rcrezende »

Yeah... my previous testcase response is wrong...
I re-submit, without a fault (precision's stuffs), and I get Accepted.

:)

Rodrigo

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

cpphamza wrote:
I have code to find intersection of 2 convex polygons, so I just used that, then compute the area of the resulting polygons.
I'm interested in implementing a convex polygon intersection algorithm, can you post your algorithm? (code, resources, links ...)

Also can anyone expalin other approaches to solve this problem?
Thanks.
The O(n) algorithm to find intersection of 2 convex polygons is related to the idea of rotating calipers.
G.T. Toussaint. A simple linear algorithm for intersecting convex polygons. The Visual Computer. 1: 118-123. 1985.

An O(n^2) algorithm is also possible, and it is pretty much just bruteforce.
Consider polygon P,Q, then for each edge of Q, compute the intersection of the half plane defined by the edge and polygon P, and update P.

If one is only interested in whether 2 convex polygon intersects, it is possible to do it in O(log n) using Chazelle and Dobkin's algorithm.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

sclo wrote:The O(n) algorithm to find intersection of 2 convex polygons is related to the idea of rotating calipers.
G.T. Toussaint. A simple linear algorithm for intersecting convex polygons. The Visual Computer. 1: 118-123. 1985.
Rotating? :D

Just sweeping left to right is enough. Imagine a vertical line through each vertex. You get O(N) strips, and in each strip at most 4 edges => each strip can be processed in O(1) time. That's all.

AxM
New poster
Posts: 5
Joined: Thu Oct 19, 2006 5:21 pm

Post by AxM »

Just sweeping left to right is enough. Imagine a vertical line through each vertex. You get O(N) strips, and in each strip at most 4 edges => each strip can be processed in O(1) time. That's all.
Could you explain the process? step by step.. I cant figure out what I have to search in each strip. If you have a link explaing this would be helpful.

Thax

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

un-precise algorithm

Post by Sedefcho »

I got ACC with a not-always-exact solution.
I take one of the triangles and start traversing its border
by doing small steps - say 1/1000 of the length of the
triangle side we are currently on.

So in about 3000 steps I get 3000 points and for each
such point I check if that point is internal for the other
triangle. That check is easy. If the point is internal then the
answer is "yes" but if all 3000 points are not internal for the
other triangle then the answer is "probably no" :) which
I just assume to be "for sure no".

I know it is stupid but it says ACC for the available input.

Post Reply

Return to “Volume 111 (11100-11199)”