点结构

struct Point {    double x;    double y;    Point(double a = 0, double b = 0) : x(a), y(b) {}};

 

1、浮点数过滤

int dbcmp(double x) {    if(x > eps)    return 1;    else if(x < -eps)    return -1;    return 0;}

2、线段求交点（简化一下可以用来判线段相交（规范相交））

 

double det(double x1, double y1, double x2, double y2) {    //求叉积    return x1*y2 - x2*y1;}double cross(Point a, Point b, Point c) {    //向量ab，和向量ac    return det(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);}double dotdet(double x1, double y1, double x2, double y2) {    //点积    return x1*x2 + y1*y2;}double dot(Point a, Point b, Point c) {    return dotdet(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);}int betweenCmp(Point a, Point b, Point c) {    //判断a是不是在bc范围内    return dbcmp(dot(a, b, c));}bool segcross(Point a, Point b, Point c, Point d) {    double s1, s2;    int d1, d2, d3, d4;    d1 = dbcmp(s1 = cross(a, b, c));    d2 = dbcmp(s2 = cross(a, b, d));    d3 = dbcmp(cross(c, d, a));    d4 = dbcmp(cross(c, d, b));    if((d1^d2) == -2 && (d3^d4) == -2) {    //规范相交        return true;    }    //非规范相交    if((d1 == 0 && betweenCmp(c, a, b) <= 0) ||       (d2 == 0 && betweenCmp(d, a, b) <= 0) ||       (d3 == 0 && betweenCmp(a, c, d) <= 0) ||       (d4 == 0 && betweenCmp(b, c, d) <= 0))        return true;    return false;}

 

 

  

3、叉积求多边形面积

double area(Point p[],int n) { //这里是相对于原点(0, 0)，也可以在多边形上找一个点作为向量的起点    double s = 0;    int i;    p[n].x = p[0].x;    p[n].y = p[0].y;    for(i = 0; i < n; ++i)        s += det(p[i].x, p[i].y, p[i+1].x, p[i+1].y);    return fabs(s / 2.0);}

4、Graham-Scan法求凸包（黑书上的优化算法）

void graham(int dir) {    int i; t = 0;    for(i = 0; i < n; ++i) {        if(vis[i])    continue;        while(t > 1 && dir*cross(p[st[t-1]], p[st[t]], p[i]) < 0)    --t;        st[++t] = i;    }    for(i = 2; i < t; ++i)    vis[st[i]] = true;}//mainfor(i = 0; i < n; ++i) {    scanf("%lf%lf", &p[i].x, &p[i].y);}sort(p, p + n, cmp);    //按y排序，如果相等，再按x排序memset(vis, 0, sizeof(vis));graham(1);for(i = 1; i <= t; ++i)    f[i] = st[i]; m = t;graham(-1);for(i = 1; i < t; ++i)    f[m + i] = st[t - i]; m += t-1;

 

ps：暂时就这些，以后还会补充。