Source (Plain Text)
#define EPS 1e-9
struct Point2 {
double x, y;
Point2 (double _x=0, double _y=0) : x(_x), y(_y) {}
};
#define DET(a,b,c,d) ((a)*(d)-(b)*(c))
#define SGN(x) ((x)<-EPS ? -1 : (x)>EPS ? 1 : 0)
#define COLLINEAR(a,b,c) (cw(a,b,c)==0)
double squaredDistance (Point2 p0, Point2 p1)
{
double dx = p1.x-p0.x;
double dy = p1.y-p0.y;
return dx*dx+dy*dy;
}
char orientation (Point2 p0, Point2 p1, Point2 p2)
{
return SGN(DET(p1.x-p0.x,p2.x-p0.x,p1.y-p0.y,p2.y-p0.y));
}
int cw (Point2 p0, Point2 p1, Point2 p2)
{
int o = orientation (p0, p1, p2);
if (o == 0) return (squaredDistance (p0, p1) < squaredDistance (p0, p2));
else
return (o == -1);
}
struct cmp_angle {
Point2 p0;
cmp_angle (Point2 p) { p0=p; }
bool operator() (const Point2& a, const Point2& b) {
return cw (p0, b, a);
}
};
bool operator< (const Point2& a, const Point2& b) {
if (fabs (a.x - b.x) < EPS) return (a.y<b.y);
return (a.x<b.x);
}