#define ISCCW 1
#define ISCW 2
#define ISON 3
inline int ccw(Coord p1, Coord p2, Coord p3) {
double d = (p1.y - p2.y)*(p3.x - p2.x) -
(p3.y - p2.y)*(p1.x - p2.x);
return (d > 1e-8) ? ISCCW :((d < -1e-8) ? ISCW : ISON);
}
inline bool between(Coord a, Coord b, Coord c) {
if(ccw(a, b, c) != ISON)
return false;
Coord p1 = b-a,
p2 = c-a;
return p2*p1 >= 0 && p2*p2 <= p1*p1;
}
inline bool between2(Coord a, Coord b, Coord c) {
if(ccw(a, b, c) != ISON)
return false;
return (a.x<=b.x && b.x <= c.x || c.x<=b.x && b.x<=a.x) &&
(a.y<=b.y && b.y<=c.y || c.y<=b.y && b.y<=a.y);
}
inline bool segsIntersect(Coord a, Coord b, Coord c, Coord d) {
if(ccw(a, b, c) == ISON || ccw(a, b, d) == ISON ||
ccw(c, d, a) == ISON || ccw(c, d, b) == ISON) {
if(between(a, b, c) || between(a, b, d) ||
between(c, d, a) || between(c, d, b))
return true;
} else {
bool ccw1 = ccw(a, b, c) == ISCCW,
ccw2 = ccw(a, b, d) == ISCCW,
ccw3 = ccw(c, d, a) == ISCCW,
ccw4 = ccw(c, d, b) == ISCCW;
return(ccw1 ^ ccw2) && (ccw3 ^ ccw4);
}
return false;
}
inline double tri_area_2(Coord a, Coord b, Coord c ) {
return a.x * b.y - a.y * b.x +
a.y * c.x - a.x * c.y +
b.x * c.y - c.x * b.y;
}
inline double tri_area(Coord a, Coord b, Coord c) {
return fabs(tri_area_2(a,b,c))/2.0;
}
inline Coord centroid(Coord a,Coord b,Coord c) {
return Coord((a.x + b.x + c.x)/3,(a.y + b.y + c.y)/3);
}
inline bool leftOf(Coord a, Coord b, Coord c) {
return tri_area_2( a, b, c ) > 0;
}
inline Position intersection( Coord a, Coord b, Coord c, Coord d) {
double s, t;
double denom;
denom =
a.x * ( d.y - c.y ) +
b.x * ( c.y - d.y ) +
d.x * ( b.y - a.y ) +
c.x * ( a.y - b.y );
if (denom == 0.0) return Position();
s = ( a.x * ( d.y - c.y ) +
c.x * ( a.y - d.y ) +
d.x * ( c.y - a.y )
) / denom;
t = -( a.x * ( c.y - b.y ) +
b.x * ( a.y - c.y ) +
c.x * ( b.y - a.y )
) / denom;
Position ret;
ret.x = a.x + s * ( b.x - a.x );
ret.y = a.y + s * ( b.y - a.y );
if ((0.0 <= s) && (s <= 1.0) &&
(0.0 <= t) && (t <= 1.0))
ret.valid = true;
else ret.valid = false;
return ret;
}