Make sure you don't overflow if you use integer arithmetics. And if you use floating point numbers make sure you make your comparisons are good (use epsilon).
Thanks for replying, but I use long long and I checked with assert that all input data fit within an int, so multiplications won't overflow and that shouldn't be a problem.
My method is as follows. I return "yes" whenever one of the following situations occurs:
1. One of the vertices of a triangle is strictly inside the other
2. Two of the sides of the triangles intersect properly.
3. One of the triangles (say ABC) has two vertices (A and B) within a side DE of the other triangle DEF, and DEC and DEF have the same orientation.
Is there anything I overlooked?
Anyway here's my code, in case someone wants to test it (I'm pretty sure the geometric functions are correct, so the problem must be elsewhere).
Code: Select all
#include <algorithm>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long tipo;
#define error 0
struct punto {
tipo x, y;
punto(tipo a = 0, tipo b = 0) : x(a), y(b) {}
bool operator==(punto &c) { return x == c.x && y == c.y; }
bool operator!=(punto &c) { return !(*this == c); }
};
typedef pair<punto, punto> segm;
punto operator-(punto a, punto b) {
return punto(a.x - b.x, a.y - b.y);
}
/* Coordenada z del producto vectorial */
tipo operator^(punto a, punto b) {
return a.x * b.y - a.y * b.x;
}
/* Devuelve 1 si el punto b est