Posted:

**Sun Oct 15, 2006 3:13 pm**Your program fails on this case:david wrote:Anyway here's my code, in case someone wants to test it.

Code: Select all

```
input:
1
0 0 5 0 2 4
4 0 6 0 -4 16
output:
pair 1: yes
```

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=37&t=12404

Page **2** of **2**

Posted: **Sun Oct 15, 2006 3:13 pm**

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

Code: Select all

```
input:
1
0 0 5 0 2 4
4 0 6 0 -4 16
output:
pair 1: yes
```

Posted: **Sun Oct 15, 2006 6:37 pm**

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

`input: 1 0 0 5 0 2 4 4 0 6 0 -4 16 output: pair 1: yes`

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

Posted: **Mon Oct 16, 2006 6:44 am**

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

0 0 1 0 1 1

0 0 1 0 1 1

Posted: **Mon Oct 16, 2006 8:42 am**

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

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

Posted: **Mon Oct 16, 2006 8:52 am**

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

Posted: **Mon Oct 16, 2006 9:11 am**

I thought so because in the sample input we have: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.

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?

Posted: **Mon Oct 16, 2006 9:17 am**

No, there isn't any common point..cpphamza wrote:I thought so because in the sample input we have: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.

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?

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

Posted: **Mon Oct 16, 2006 11:01 am**

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)

Posted: **Mon Oct 16, 2006 12:54 pm**

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

Also can anyone expalin other approaches to solve this problem?

Thanks.

Posted: **Mon Oct 16, 2006 3:06 pm**

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

Posted: **Mon Oct 16, 2006 7:52 pm**

Yeah... my previous testcase response is wrong...

I re-submit, without a fault (precision's stuffs), and I get Accepted.

Rodrigo

I re-submit, without a fault (precision's stuffs), and I get Accepted.

Rodrigo

Posted: **Tue Oct 17, 2006 12:30 am**

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

Also can anyone expalin other approaches to solve this problem?

Thanks.

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.

Posted: **Tue Oct 17, 2006 12:40 am**

Rotating?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.

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.

Posted: **Sat Oct 21, 2006 8:38 am**

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

Thax

Posted: **Thu Nov 23, 2006 4:44 pm**

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.

I take one of the triangles and start traversing its border

by doing small steps - say 1/1000 of the length of the

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.