OJ Board

My algorithm is quite simple, but I keep getting WA.

If the 2 triangles are on parallel planes {
if the planes do not intersect, then return 0
else {
if any pair of line segments between different triangle intersect, return 1
if any triangle is contained in another triangle, return 1
else return 0
}
}
else {
compute L, the line of intersection between the 2 planes.
compute intervals on L where the line segments of the triangle intersects L
if the interval overlaps, then return 1
else return 0
}

What is wrong with my approach? I notice that the acceptance ratio is quite low.

Actually, the acceptance rate is quite high, but after i got about 10 WAs it began to drop. BTW, i used the same algorithm as yours. My code for this problem is 300 lines. I think it is quite long and small mistakes can appear here and there.

Actually, is there any problem with using epsilons everywhere? I mean, are there any cases where the difference is close to epsilon?

I used epsilon=1e-6 just like the description said and i used it everywhere. I even used it for the distance between points after i had projected them in some 2D plane. So maybe the epsilon is not so important.

My AC code's epsilon is 1e-8.

Your algorithm is right, but notice the problem statement: "if the distance between two points is equal or less than 1e-6, they are regarded as one point". So you should consider these situations:

1. If the distance between one endpoint of triangle A and one edge of triangle B is equal or less than 1e-6, return true.

2. if triangle A's one endpoint's projection on plane B falls inside triangle B, and the endpoint's distance to plane B is equal or less than 1e-6, return true.

And as my test, the situation 1 appears in the test cases, but situation 2 doesn't.

You can test your i/o on this really useful website by Greve.

http://uva.xgd.dk/problemssolve.php


It lets you enter input, and gives you output file.

This question is quite crazy. I've tried many algorithms from Möller to Held to even Guigue but they all took more than 2 seconds and TLEd. I nearly gave up until I tried an algorithm from Hao Shen, Pheng Ann Heng and Zesheng Tang which was the only one which took less than a second to complete. Amazing stuff. I never knew calculating the intersection of two triangles in 3D space would take so much work. Here is an implementation of the algorithm: http://jgt.akpeters.com/papers/ShenHengTang03/
Good luck.