平面计算几何模板

https://vjudge.net/problem/UVA-12304
大白书 267

#include<cmath>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
const double EPS = 1e-10;
const  double PI=acos(-1);
using namespace std;
struct Point{
     double x;
     double y;
    Point( double x=0, double y=0):x(x),y(y){}
    //void operator<<(Point &A) {cout<<A.x<<' '<<A.y<<endl;}
};

int dcmp(double x) {
    if(fabs(x) < EPS) return 0;
    else return x < 0 ? -1 : 1;
}

typedef  Point  Vector;

Vector  operator +(Vector A,Vector B) { return Vector(A.x+B.x,A.y+B.y);}

Vector  operator -(Vector A,Vector B) { return Vector(A.x-B.x,A.y-B.y); }

Vector  operator *(Vector A, double p) { return Vector(A.x*p,A.y*p);  }

Vector  operator /(Vector A, double p) {return Vector(A.x/p,A.y/p);}

ostream &operator<<(ostream & out,Point & P) { out<<P.x<<' '<<P.y<<endl; return out;}

bool  operator< (const Point &A,const Point &B) { return dcmp(A.x-B.x)<0||(dcmp(A.x-B.x)==0&&dcmp(A.y-B.y)<0); }

bool  operator== ( const Point &A,const Point &B) { return dcmp(A.x-B.x)==0&&dcmp(A.y-B.y)==0;}

//向量点积
 double  dot(Vector A,Vector B) {return A.x*B.x+A.y*B.y;}
//向量叉积
 double  cross(Vector A,Vector B)  {return A.x*B.y-B.x*A.y; }

//向量长度
 double  length(Vector A)  { return sqrt(dot(A, A));}

//向量夹角
 double  angle(Vector A,Vector B) {return acos(dot(A,B)/length(A)/length(B));}

 //三角形有向面积的二倍
 double  area2(Point A,Point B,Point C ) {return cross(B-A, C-A);}

 //向量逆时针旋转rad度(弧度)
Vector rotate(Vector A, double rad) { return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}

//计算向量A的单位法向量。左转90°，把长度归一。调用前确保A不是零向量。
Vector normal(Vector A) { double L=length(A);return Vector(-A.y/L,A.x/L);}

/************************************************************************
使用复数类实现点及向量的简单操作

#include <complex>
typedef complex<double> Point;
typedef Point Vector;

double dot(Vector A, Vector B) { return real(conj(A)*B)}
double cross(Vector A, Vector B) { return imag(conj(A)*B);}
Vector rotate(Vector A, double rad) { return A*exp(Point(0, rad)); }

*************************************************************************/

/****************************************************************************
* 用直线上的一点p0和方向向量v表示一条指向。直线上的所有点P满足P = P0+t*v;
* 如果知道直线上的两个点则方向向量为B-A, 所以参数方程为A+(B-A)*t;
* 当t 无限制时， 该参数方程表示直线。
* 当t > 0时， 该参数方程表示射线。
* 当 0 < t < 1时， 该参数方程表示线段。
*****************************************************************************/

//直线交点,须确保两直线有唯一交点。
Point getLineIntersection(Point P,Vector v,Point Q,Vector w)
{
    Vector u=P-Q;
     double t=cross(w, u)/cross(v,w);
    return P+v*t;

}
//点到直线距离
 double distanceToLine(Point P,Point A,Point B)
{
    Vector v1=P-A; Vector v2=B-A;
    return fabs(cross(v1,v2))/length(v2);

}

//点到线段的距离
 double distanceToSegment(Point P,Point A,Point B)
{
    if(A==B)  return length(P-A);

    Vector v1=B-A;
    Vector v2=P-A;
    Vector v3=P-B;

    if(dcmp(dot(v1,v2))==-1)    return  length(v2);
    else if(dot(v1,v3)>0)    return length(v3);

    else return distanceToLine(P, A, B);

}

//点在直线上的投影
Point getLineProjection(Point P,Point A,Point B)
{
    Vector v=B-A;
    Vector v1=P-A;
     double t=dot(v,v1)/dot(v,v);

    return  A+v*t;
}

//线段相交判定，交点不在一条线段的端点
bool  segmentProperIntersection(Point a1,Point a2,Point b1,Point b2)
{
     double c1=cross(b1-a1, a2-a1);
     double c2=cross(b2-a1, a2-a1);
     double c3=cross(a1-b1, b2-b1);
     double c4=cross(a2-b1, b2-b1);

    return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0 ;

}

//判断点是否在点段上，不包含端点
bool  onSegment(Point P,Point A,Point B)
{
    return dcmp(cross(P-A, P-B))==0&&dcmp(dot(P-A,P-B))<0;
}

//计算凸多边形面积
double convexPolygonArea(Point *p, int n) {
    double area = 0;
    for(int i = 1; i < n-1; i++)
        area += cross(p[i] - p[0], p[i+1] - p[0]);
    return area/2;
}

//计算多边形的有向面积
 double polygonArea(Point *p,int n)
{
     double area=0;

    for(int i=1;i<n-1;i++)
    {
        area+=cross(p[i]-p[0], p[i+1]-p[0]);

    }
    return area/2;

}

/***********************************************************************
* Morley定理：三角形每个内角的三等分线，相交成的三角形是等边三角形。
* 欧拉定理：设平面图的定点数，边数和面数分别为V,E,F。则V+F-E = 2;
************************************************************************/
Point  read_point()
{
    Point P;
    scanf("%lf%lf",&P.x,&P.y);
    return  P;
}

struct Circle
{
    Point c;
     double r;

    Circle(Point c=Point(0,0), double r=0):c(c),r(r) {}
    
    //通过圆心角确定圆上坐标
    Point point( double a)
    {
        return Point(c.x+r*cos(a),c.y+r*sin(a));
    }

};

struct  Line
{
    Point p;
    Vector v;
    double ang;
    Line(Point p=Point(0,0),Vector v=Vector(0,1)):p(p),v(v) {}

    Point point( double t)
    {
        return Point(p+v*t);
    }
    bool operator < (const Line& L) const {
        return ang < L.ang;
    }
};


//直线和圆的交点，返回交点个数，结果存在sol中。
//该代码没有清空sol。
int getLineCircleIntersection(Line L,Circle cir, double &t1, double &t2,vector<Point> &sol)
{
     double a=L.v.x;
     double b=L.p.x-cir.c.x;
     double c=L.v.y;
     double d=L.p.y-cir.c.y;

     double e=a*a+c*c;
     double f=2*(a*b+c*d);
     double g=b*b+d*d-cir.r*cir.r;

     double delta=f*f-4*e*g;

    if(dcmp(delta)<0) return 0;

    if(dcmp(delta)==0)
    {
        t1=t2=-f/(2*e);
        sol.push_back(L.point(t1));
        return 1;
    }
    else
    {
        t1=(-f-sqrt(delta))/(2*e);
        t2=(-f+sqrt(delta))/(2*e);

        sol.push_back(L.point(t1));
        sol.push_back(L.point(t2));

        return 2;
    }

}

// 向量极角公式
 double angle(Vector v)  {return atan2(v.y,v.x);}

 //两圆相交
int getCircleCircleIntersection(Circle C1,Circle C2,vector<Point> &sol)
{
     double d=length(C1.c-C2.c);

     if(dcmp(d)==0)
     {
         if(dcmp(C1.r-C2.r)==0)  return -1;  // 重合
         else return 0;    //  内含  0 个公共点
     }

    if(dcmp(C1.r+C2.r-d)<0)  return 0;  // 外离
    if(dcmp(fabs(C1.r-C2.r)-d)>0)  return 0;  // 内含

     double a=angle(C2.c-C1.c);
     double da=acos((C1.r*C1.r+d*d-C2.r*C2.r)/(2*C1.r*d));

    Point p1=C1.point(a-da);
    Point p2=C1.point(a+da);

    sol.push_back(p1);

    if(p1==p2)  return 1; // 相切
    else
    {
        sol.push_back(p2);
        return 2;
    }
}


//过定点做圆的切线
//过点p做圆C的切线，返回切线个数。v[i]表示第i条切线
int getTangents(Point p,Circle cir,Vector *v)
{
    Vector u=cir.c-p;

     double dist=length(u);

    if(dcmp(dist-cir.r)<0)  return 0;

    else if(dcmp(dist-cir.r)==0)
    {
        v[0]=rotate(u,PI/2);
        return 1;
    }
    else
    {

         double ang=asin(cir.r/dist);
        v[0]=rotate(u,-ang);
        v[1]=rotate(u,+ang);
        return 2;
    }
}

//两圆的公切线
//返回切线的个数，-1表示有无数条公切线。
//a[i], b[i] 表示第i条切线在圆A，圆B上的切点
int getTangents(Circle A, Circle B, Point *a, Point *b) {
    int cnt = 0;
    if(A.r < B.r) {
        swap(A, B); swap(a, b);
    }
    int d2 = (A.c.x - B.c.x)*(A.c.x - B.c.x) + (A.c.y - B.c.y)*(A.c.y - B.c.y);
    int rdiff = A.r - B.r;
    int rsum = A.r + B.r;
    if(d2 < rdiff*rdiff) return 0;   //内含
    double base = atan2(B.c.y - A.c.y, B.c.x - A.c.x);
    if(d2 == 0 && A.r == B.r) return -1;   //无限多条切线
    if(d2 == rdiff*rdiff) {         //内切一条切线
        a[cnt] = A.point(base);
        b[cnt] = B.point(base);
        cnt++;
        return 1;
    }
    //有外共切线
    double ang = acos((A.r-B.r) / sqrt(d2));
    a[cnt] = A.point(base+ang); b[cnt] = B.point(base+ang); cnt++;
    a[cnt] = A.point(base-ang); b[cnt] = B.point(base-ang); cnt++;
    if(d2 == rsum*rsum) {  //一条公切线
        a[cnt] = A.point(base);
        b[cnt] = B.point(PI+base);
        cnt++;
    } else if(d2 > rsum*rsum) {   //两条公切线
        double ang = acos((A.r + B.r) / sqrt(d2));
        a[cnt] = A.point(base+ang); b[cnt] = B.point(PI+base+ang); cnt++;
        a[cnt] = A.point(base-ang); b[cnt] = B.point(PI+base-ang); cnt++;
    }
    return cnt;
}

typedef vector<Point> Polygon;

//点在多边形内的判定
int isPointInPolygon(Point p, Polygon poly) {
    int wn = 0;
    int n = poly.size();
    for(int i = 0; i < n; i++) {
        if(onSegment(p, poly[i], poly[(i+1)%n])) return -1; //在边界上
        int k = dcmp(cross(poly[(i+1)%n]-poly[i], p-poly[i]));
        int d1 = dcmp(poly[i].y - p.y);
        int d2 = dcmp(poly[(i+1)%n].y - p.y);
        if(k > 0 && d1 <= 0 && d2 > 0) wn++;
        if(k < 0 && d2 <= 0 && d1 > 0) wn++;
    }
    if(wn != 0) return 1;       //内部
    return 0;                   //外部
}

//凸包
/***************************************************************
* 输入点数组p， 个数为p， 输出点数组ch。 返回凸包顶点数
* 不希望凸包的边上有输入点，把两个<= 改成 <
* 高精度要求时建议用dcmp比较
* 输入点不能有重复点。函数执行完以后输入点的顺序被破坏
****************************************************************/
int convexHull(Point *p, int n, Point* ch) {
    sort(p, p+n);      //先比较x坐标，再比较y坐标
    int m = 0;
    for(int i = 0; i < n; i++) {
        while(m > 1 && cross(ch[m-1] - ch[m-2], p[i]-ch[m-2]) <= 0) m--;
        ch[m++] = p[i];
    }
    int k = m;
    for(int i = n-2; i >= 0; i++) {
        while(m > k && cross(ch[m-1] - ch[m-2], p[i]-ch[m-2]) <= 0) m--;
        ch[m++] = p[i];
    }
    if(n > 1) m--;
    return m;
}

//用有向直线A->B切割多边形poly， 返回“左侧”。 如果退化，可能会返回一个单点或者线段
//复杂度O(n2);
Polygon cutPolygon(Polygon poly, Point A, Point B) {
    Polygon newpoly;
    int n = poly.size();
    for(int i = 0; i < n; i++) {
        Point C = poly[i];
        Point D = poly[(i+1)%n];
        if(dcmp(cross(B-A, C-A)) >= 0) newpoly.push_back(C);
        if(dcmp(cross(B-A, C-D)) != 0) {
            Point ip = getLineIntersection(A, B-A, C, D-C);
            if(onSegment(ip, C, D)) newpoly.push_back(ip);
        }
    }
    return newpoly;
}

//半平面交
//点p再有向直线L的左边。（线上不算）
bool onLeft(Line L, Point p) {
    return cross(L.v, p-L.p) > 0;
}

//两直线交点，假定交点唯一存在
Point getIntersection(Line a, Line b) {
    Vector u = a.p - b.p;
    double t = cross(b.v, u) / cross(a.v, b.v);
    return a.p+a.v*t;
}

int halfplaneIntersection(Line* L, int n, Point* poly) {
    sort(L, L+n);               //按极角排序

    int first, last;            //双端队列的第一个元素和最后一个元素
    Point *p = new Point[n];    //p[i]为q[i]和q[i+1]的交点
    Line *q = new Line[n];      //双端队列
    q[first = last = 0] = L[0]; //队列初始化为只有一个半平面L[0]
    for(int i = 0; i < n; i++) {
        while(first < last && !onLeft(L[i], p[last-1])) last--;
        while(first < last && !onLeft(L[i], p[first])) first++;
        q[++last] = L[i];
        if(fabs(cross(q[last].v, q[last-1].v)) < EPS) {
            last--;
            if(onLeft(q[last], L[i].p)) q[last] = L[i];
        }
        if(first < last) p[last-1] = getIntersection(q[last-1], q[last]);
    }
    while(first < last && !onLeft(q[first], p[last-1])) last--;
    //删除无用平面
    if(last-first <= 1) return 0;   //空集
    p[last] = getIntersection(q[last], q[first]);

    //从deque复制到输出中
    int m = 0;
    for(int i = first; i <= last; i++) poly[m++] = p[i];
    return m;
}

// 求内切圆坐标
Circle inscribledCircle(Point p1,Point p2,Point p3)
{
    double a=length(p2-p3);
    double b=length(p3-p1);
    double c=length(p1-p2);

    Point I=(p1*a+p2*b+p3*c)/(a+b+c);

    return Circle(I,distanceToLine(I, p1, p2));

}

//求外接圆坐标
Circle circumscribedCircle(Point p1,Point p2,Point p3)
{
    double Bx=p2.x-p1.x,By=p2.y-p1.y;
    double Cx=p3.x-p1.x,Cy=p3.y-p1.y;

    double D=2*(Bx*Cy-By*Cx);

    double cx=(Cy*(Bx*Bx+By*By)-By*(Cx*Cx+Cy*Cy))/D+p1.x;
    double cy=(Bx*(Cx*Cx+Cy*Cy)-Cx*(Bx*Bx+By*By))/D+p1.y;

    Point p=Point(cx,cy);

    return Circle(p,length(p-p1));
}

int main()
{
    char str[50];
    Point A,B,C;
    while(scanf("%s",str)!=EOF)
    {
          if(!strcmp(str,"CircumscribedCircle"))
          {
              A=read_point();
              B=read_point();
              C=read_point();
              Circle cir=circumscribedCircle(A, B, C);
              printf("(%.6f,%.6f,%.6f)\n",cir.c.x,cir.c.y,cir.r);
          }

          else if(!strcmp(str,"InscribedCircle"))
          {
              A=read_point();
              B=read_point();
              C=read_point();
              Circle cir=inscribledCircle(A, B, C);
              printf("(%.6f,%.6f,%.6f)\n",cir.c.x,cir.c.y,cir.r);

          }
          else if(!strcmp(str,"TangentLineThroughPoint"))
          {
              Circle  cir;
              cir.c=read_point();
              scanf("%lf",&cir.r);
              Point p=read_point();
              Vector vec[2];
               double val[2];
              int ans=getTangents(p, cir,vec);
              if(ans)
              {
                    for(int i=0;i<ans;i++)     // atan2 返回的极角范围是-PI到PI
                    {
                        if(dcmp(angle(vec[i]))<0)
                        {
                            val[i]=(angle(vec[i])+PI)/PI*180;
                        }
                        else  val[i]=angle(vec[i])/PI*180;
                        if(dcmp(val[i]-180.0)==0) val[i]=0.0;
                    }

                sort(val,val+ans);
                printf("[");
                for(int i=0;i<ans-1;i++)
                printf("%.6f,",val[i]);
                printf("%.6f]\n",val[ans-1]);
              }
              else
              {
                  printf("[]\n");

              }
          }
          else if(!strcmp(str,"CircleThroughAPointAndTangentToALineWithRadius"))
          {
              Point p=read_point();
              Point A=read_point();
              Point B=read_point();
               double r;
              scanf("%lf",&r);

              Vector dir=B-A;
              Vector v1=normal(dir);
              Vector v2=rotate(v1, PI);

              Point p1=A+v1*r;
              Point p2=A+v2*r;

              Line L1=Line(p1,dir);
              Line L2=Line(p2,dir);

              vector<Point> sol;

               double t1=0,t2=0;

              int ans=getLineCircleIntersection(L1, Circle(p,r), t1, t2,sol);

              ans+=getLineCircleIntersection(L2, Circle(p,r), t1, t2, sol);

              if(!ans)
              {
                  printf("[]\n");

              }

              else
              {
                  sort(sol.begin(),sol.end());
                  printf("[");
                  for(int i=0;i<ans-1;i++)
                      printf("(%.6f,%.6f),",sol[i].x,sol[i].y);
                  printf("(%.6f,%.6f)]\n",sol[ans-1].x,sol[ans-1].y);
              }


          }

           else if(!strcmp(str,"CircleTangentToTwoLinesWithRadius"))
           {
               Point A1=read_point(),B1=read_point(),A2=read_point(),B2=read_point();

                double r;
               scanf("%lf",&r);


               Vector v1=B1-A1;
               Vector v2=B2-A2;

               Vector normal_1_1=normal(v1);
               Vector normal_1_2=rotate(normal_1_1, PI);

               Point  p1=A1+normal_1_1*r;
               Point  p2=A1+normal_1_2*r;
               
               Vector normal_2_1=normal(v2);
               Vector normal_2_2=rotate(normal_2_1, PI);

               Point  p3=A2+normal_2_1*r;
               Point  p4=A2+normal_2_2*r;
               
               vector<Point>  ans;

               ans.push_back(getLineIntersection(p1, v1, p3, v2));
               ans.push_back(getLineIntersection(p1, v1, p4, v2));

               ans.push_back(getLineIntersection(p2, v1, p3, v2));
               ans.push_back(getLineIntersection(p2, v1, p4, v2));

               sort(ans.begin(),ans.end());

               printf("[");
               for(int i=0;i<3;i++)
                   printf("(%.6f,%.6f),",ans[i].x,ans[i].y);

               printf("(%.6f,%.6f)]\n",ans[3].x,ans[3].y);

           }

           else if(!strcmp(str,"CircleTangentToTwoDisjointCirclesWithRadius"))
           {
               Circle A,B;
               A.c=read_point();
               scanf("%lf",&A.r);
               B.c=read_point();
               scanf("%lf",&B.r);

                double r;
               scanf("%lf",&r);

               vector<Point> ans;
               int cnt=getCircleCircleIntersection(Circle(A.c,A.r+r), Circle(B.c,B.r+r), ans);

               if(!cnt)
               {
                   printf("[]\n");
               }
               else
               {
               sort(ans.begin(),ans.end());

               printf("[");
               for(int i=0;i<cnt-1;i++)
                   printf("(%.6f,%.6f),",ans[i].x,ans[i].y);

               printf("(%.6f,%.6f)]\n",ans[cnt-1].x,ans[cnt-1].y);
               
               }
           }
    }
}