学步园

ps: 打计算几何模板的时候一定要细心，没把握时要多检查，很多时候就是打模板出错。

#include<cmath>

#define max(a, b)((a)>(b)?(a):(b))   //  代码尽量简洁点。
#define min(a, b)((a)<(b)?(a):(b)) 

const double eps = 1e-8;

structPoint{      // 点的表示。
    double x,y;
};
structLine{       //  直线的表示。
    double a, b,c;
};

structSegment{    //  线段的表示。
    Point a,b;
};
structTriangle{    // 三角形的表示。
    Point a, b,c;
};
structRectangle{   // 矩形的表示。
    Point a, b,c, d;
};
structPolygon{    //  多边形的表示。
    int n;
    Pointp[Max];
};
structCircle{     //  圆的表示。
    doubler;
    Pointcenter;
};

double mydis(Point p1, Point p2){
    returnsqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));

} 

则判断PP1与PP2的点积结果的符号，用u·v表示。通用公式：|u||v|cos<u,v>。
„ 若PP1•PP2 < 0，则P在P1P2内部
„ 若PP1•PP2 > 0，则P在P1P2外部
„ 若PP1•PP2 = 0，则P与P1或P2重合

* 由两点求边的方程，运用(x2-x1)(y-y1) = (y2-y1)(x-x1)。

Line getLine(Point p1, Point p2){ 

    Linetmp;
    tmp.a = p1.y- p2.y;
    tmp.b = p2.x- p1.x;
    tmp.c =p1.x*p2.y - p2.x*p1.y;
    returntmp;
}

* 判断两直线是否平行。

bool parallel(Line l1, Linel2){  

   return abs(l1.a*l2.b -l2.a*l1.b) < eps;
}

* 判断两直线是否重合。

bool lineEqual(Line l1, Linel2){    

   if(!parallel(l1, l2)) return false;
    returnabs(l1.a*l2.c - l2.a*l1.c) < eps&& abs(l1.b*l2.c - l2.b*l1.c)< eps;
}

* 求两相交直线的交点。

Point getIntersect(Line l1, Line l2){

    Pointtmp;
    tmp.x =(l1.b*l2.c - l2.b*l1.c) / (l1.a*l2.b - l2.a*l1.b);
    tmp.y =(l1.c*l2.a - l2.c*l1.a) / (l1.a*l2.b - l2.a*l1.b);
    returntmp;
}

* 知道直线上两点p1p2，判断直线与线段是否相交，含顶点。

double mult(Point sp, Point ep, Point op){
   return (sp.x-op.x)*(ep.y-op.y) - (ep.x-op.x)*(sp.y-op.y);
}

bool isIntersected(Point p1, Point p2, Point s,Point e){
    if(mult(p1,p2, s)*mult(p1, p2, e) > eps) return false;
    returntrue;
}

* 1判断两线段是否相交，含顶点。

double mult(Point sp, Point ep, Point op){
    return(sp.x-op.x)*(ep.y-op.y) - (ep.x-op.x)*(sp.y-op.y);
}

bool isIntersected(Point s1, Point e1, Point s2,Point e2){
    if(min(s1.x, e1.x) <= max(s2.x, e2.x)&&
       min(s1.y, e1.y) <= max(s2.y, e2.y)&&
       min(s2.x, e2.x) <= max(s1.x, e1.x)&&
       min(s2.y, e2.y) <= max(s1.y, e1.y)&&
       mult(s2, e2, s1) * mult(s2, e2, e1) <= 0&&
       mult(s1, e1, s2) * mult(s1, e1, e2) <= 0)
       return true;
    returnfalse;
}

* 2判断两线段是否相交，不含顶点。

int dblcmp(double r){
    if(fabs(r)< eps) return 0;
    return r> 0 ? 1 : -1;
}

double dot(double x1, double y1, double x2, double y2){
    return x1*y2- x2*y1;
}

double cross(Point a, Point b, Point c){
    returndot(b.x-a.x, b.y-a.y, c.x-a.x, c.y-a.y);
}

bool isIntersected(Point a, Point b, Point c, Point d){
    return(dblcmp(cross(a,b,c))^dblcmp(cross(a,b,d))) == -2
     &&(dblcmp(cross(c,d,a))^dblcmp(cross(c,d,b))) == -2;
}

* 求两条不重复相交线段的交点。

Point getInter(Point s1, Point e1, Point s2, Point e2){

    Point tmp= s1;
    double t =((s1.x-s2.x)*(s2.y-e2.y) - (s1.y-s2.y)*(s2.x-e2.x))
           /((s1.x-e1.x)*(s2.y-e2.y) - (s1.y-e1.y)*(s2.x-e2.x));
    tmp.x +=(e1.x-s1.x) * t;
    tmp.y +=(e1.y-s1.y) * t;
    returntmp;
}

* 1求凸包：1.求之前判断是否够3个顶点，2.求之后判断是否为一条直线：top <3，3.求后记得用res[]？

bool cmp(Point &a, Point&b){
   if(a.y == b.y) return a.x < b.x;
   return a.y < b.y;
}

bool mult(Point sp, Point ep, Point op){
   return (sp.x-op.x)*(ep.y-op.y) >=(ep.x-op.x)*(sp.y-op.y);
}

  //n为原图的点数，p[]为原图的点（0~n-1），top为凸包点的数量（0~top-1），res[]为凸包点的下标，。

void Graham(int res[], int n, Pointp[]){  

   int i, len;

    top =1;

   sort(p, p+n, cmp);

    for(i =0; i < 3；i ++) res[i]= i;
   for(i = 2; i < n; i ++){
       while(top && mult(p[i],p[res[top]], p[res[top-1]])) top --;
       res[++ top] = i;
   }
   len = top;
   res[++ top] = n-2;
   for(i = n - 3; i >= 0; i --){
       while(top != len && mult(p[i],p[res[top]], p[res[top-1]])) top --;
       res[++ top] = i;
   }

}

* 求多边形面积，凹凸都可以，p[]必为按照逆时针方向存储。

double area(int n, Point p[]) {
    doubles; 
    if (n< 3) return 0; 
    s = p[0].y *(p[n-1].x-p[1].x); 
    for (int i =1;i < n;i ++) 
       s += p[i].y *( p[i-1].x-p[(i+1)%n].x); 
    returns/2;
}