平面计算几何模板

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);
               
               }
           }
    }
}
最后编辑于
?著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,128评论 6 493
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,316评论 3 388
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事?!?“怎么了?”我有些...
    开封第一讲书人阅读 159,737评论 0 349
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,283评论 1 287
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,384评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,458评论 1 292
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,467评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,251评论 0 269
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,688评论 1 306
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,980评论 2 328
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,155评论 1 342
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,818评论 4 337
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,492评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,142评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,382评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,020评论 2 365
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,044评论 2 352

推荐阅读更多精彩内容

  • afinalAfinal是一个android的ioc,orm框架 https://github.com/yangf...
    passiontim阅读 15,417评论 2 45
  • 今年7月份,在璐璐的指导下,我开始系统性地读书,之所以这么说,是要同过去那种漫无目的、走马观花式的读书区分开来。关...
    萧萧语歌阅读 236评论 0 1