UVA 12304 /// 圆的综合题圆的模板

题目大意：

①给出三角形三个点，求三角形外接圆，求外接圆的圆心和半径。

②给出三角形三个点，求三角形内接圆，求内接圆的圆心和半径。

③给出一个圆，和一个点，求过该点的圆的切线与x轴的夹角（0<=angle<180）；

④给出一条直线，一个点p，指定半径r，求经过点p的与直线相切的半径为r的圆；

⑤给出两条直线，求与这两条直线相切的圆；

⑥给出两个圆，求同时与这两个圆相切的圆；

贴一下圆的模板带了一些注释

主要包括以下内容

// 求三角形abc的外接圆c（圆心、半径）

C csC(P a,P b,P c)

// 求三角形abc的内接圆c（圆心、半径）

C isC(P a,P b,P c)

// 直线l与圆c的交点返回个数交点坐标存入s

int insLC(L l,C c,vector& s)

// 圆c1与c2的交点返回个数交点坐标存入s

int insCC(C c1,C c2,vector& s)

// 过点p求与圆c相切的切线返回条数切线向量存入v

int PCgetL(P p,C c,vector & v)

// 过点p求与直线l相切的半径为r的圆返回个数圆心坐标存入ans

int PLgetC(P p,L l,double r,vector & ans)

// 求与直线l1和l2相切的半径为r的圆返回个数圆心坐标存入ans

int LLgetC(L l1,L l2,double r,vector& ans)

// 求圆c1和c2的公切线返回条数切线与c1的交点存入ansa 与c2的交点存入ansb

int CCgetL(C c1,C c2,vector & ansa,vector & ansb)

// 求圆c1与c2的相交面积（本题中无用只是顺便贴一下）

double insAreaCC(P c1, double r1, P c2, double r2)

// 求n个点的最小圆覆盖（圆心、半径）

C MCC()

解法其实也多种多样这里放两份题解

https://www.cnblogs.com/dilthey/p/7758012.html

https://blog.csdn.net/peteryuanpan/article/details/40315381

#include <bits/stdc++.h>

#define pb(a) push_back(a)

#define PI acos(-1)

using namespace std;

const double eps=1e-;

double add(double a,double b) {

    if(abs(a+b)<eps*(abs(a)+abs(b))) return ;

    return a+b;

}

struct P {

    double x,y;

    P(){}

    P(double _x,double _y):x(_x),y(_y){}

    P operator - (P p) {

        return P(add(x,-p.x),add(y,-p.y)); }

    P operator + (P p) {

        return P(add(x,p.x),add(y,p.y)); }

    P operator * (double d) {

        return P(x*d,y*d); }

    P operator / (double d) {

        return P(x/d,y/d); }

    double dot (P p) {

        return add(x*p.x,y*p.y); }

    double det (P p) {

        return add(x*p.y,-y*p.x); }

    bool operator == (const P& p)const {

        return abs(x-p.x)<eps && abs(y-p.y)<eps; }

    bool operator < (const P& p)const {

        return x<p.x || (x==p.x && y<p.y);

    }

    void read() {

        scanf("%lf%lf",&x,&y); }

};

struct L {

    P p, v;

    double ang;

    L(){}

    L(P _p,P _v):p(_p),v(_v){ ang=atan2(v.y,v.x); }

    P acP(double t) {

        return p+v*t;

    }

};

struct C {

    P p; double r;

    C(){}

    C(P _p,double _r):p(_p),r(_r){}

    P acP(double a) {

        return P(p.x+cos(a)*r,p.y+sin(a)*r);

    }

    void read() {

        scanf("%lf%lf%lf",&p.x,&p.y,&r); }

};

// 求向量a的长度

double lenP(P a) {

    return sqrt(a.dot(a));

}

// 求向量v的垂直单位向量

P normal(P v) {

    double len=lenP(v);

    return P(-v.y/len,v.x/len);

}

// 求旋转ang后的向量v

P Rotate(P v,double ang) {

    P u=P(sin(ang),cos(ang));

    return P(v.det(u),v.dot(u));

}

// 求两向量夹角

double Angle(P u,P v) {

    return acos(u.dot(v)/lenP(u)/lenP(v));

}

// 求向量v极角

double angle(P v) {

    return atan2(v.y,v.x);

}

// 求点c到直线ab距离

double lenPL(P a,P b,P c) {

    if(a==b) return lenP(a-c);

    if((b-a).dot(c-a)<) return lenP(a-c);

    else if((b-a).dot(c-b)>) return lenP(b-c);

    else return abs((c-a).det(b-a))/lenP(a-b);

}

// 求两直线交点

P ins(L a,L b) {

    P v=a.p-b.p, v1=a.v, v2= b.v;

    double t=v2.det(v)/v1.det(v2);

    return a.p+v1*t;

}

/*求直线l与圆c的交点个数

t1 t2为交点对应的圆心角

交点存入s中

*/

int insLC(L l,C c,vector<P>& s) {

    double ta=l.v.x, tb=l.p.x-c.p.x;

    double tc=l.v.y, td=l.p.y-c.p.y;

    double A=ta*ta+tc*tc, B=*(ta*tb+tc*td), C=tb*tb+td*td-c.r*c.r;

    double delta=B*B-4.0*A*C;

    double t1,t2; // 圆心角

    if(delta<-eps) return ; // <0无解

    else if(abs(delta)<eps) { // =0存在一个解

        t1=t2=-B/(2.0*A); s.pb(l.acP(t1));

        return ;

    }

    else { // 两个解

        t1=(-B-sqrt(delta))/(2.0*A); s.pb(l.acP(t1));

        t2=(-B+sqrt(delta))/(2.0*A); s.pb(l.acP(t2));

        return ;

    }

}

/* 判断两圆相交

求圆c1与c2的交点 并用s保存交点

*/

int insCC(C c1,C c2,vector<P>& s) {

    double d=lenP(c1.p-c2.p);

    if(abs(d)<eps) {

        if(abs(c1.r-c2.r)<eps) return -; // 重合

        return ; // 内含

    }

    if((c1.r+c2.r-d)<-eps) return ; // 外离

    if(d-abs(c1.r-c2.r)<-eps) return ; // 内离

    double ang=angle(c2.p-c1.p); // 向量c1c2求极角

    double da=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(*c1.r*d));

    // c1与交点的向量 与 c1c2 的夹角

    P p1=c1.acP(ang-da), p2=c1.acP(ang+da); // 求得两交点

    s.pb(p1);

    if(p1==p2) return ; // 同一个点

    s.pb(p2); return ;

}

/*求三角形的外接圆（圆心、半径）

*/

C csC(P a,P b,P c) {

    double bx=b.x-a.x, by=b.y-a.y;

    double cx=c.x-a.x, cy=c.y-a.y;

    double d=*(cy*bx-cx*by);

    double x=(cy*(bx*bx+by*by)-by*(cx*cx+cy*cy))/d+a.x;

    double y=(bx*(cx*cx+cy*cy)-cx*(bx*bx+by*by))/d+a.y;

    P r(x,y);

    return C(r,lenP(a-r));

}

/*求三角形的内接圆（圆心、半径）

*/

C isC(P a,P b,P c) {

    double d=lenP(b-c), e=lenP(c-a), f=lenP(a-b);

    P p=(a*d+b*e+c*f)/(d+e+f);

    return C(p,lenPL(a,b,p));

}

/*过定点p作圆c的切线l

得p到圆心的向量（固定方向）求距离dist 判断距离

旋转向量（以p点为心旋转）得到切线向量 并存入v

*/

int PCgetL(P p,C c,vector <P>& v) {

    P u=c.p-p; // p到圆心的向量

    double dist=lenP(u);

    if(dist-c.r<-eps) return ; // p在圆内

    else if(abs(dist-c.r)<eps) { // p在圆上

        v.pb(Rotate(u,PI/)); return ;

    }

    else {

        double ang=asin(c.r/dist); // 切线与u的夹角

        v.pb(Rotate(u,-ang));

        v.pb(Rotate(u,ang));

        return ;

    }

}

/*过点p与直线l相切的半径为r的圆

以点p为圆心r为半径得到圆pc

直线l向上和向下平移r后得到lup和ldw

得到圆pc与直线lup和ldw的交点 就是圆心 并存入ans

*/

int PLgetC(P p,L l,double r,vector <P>& ans) {

    P v=normal(l.v); v=v/lenP(v)*r;

    L lup(l.p+v,l.v), ldw(l.p-v,l.v);

    int c1=insLC(lup,C(p,r),ans);

    int c2=insLC(ldw,C(p,r),ans);

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

    return c1+c2;

}

/*与两条相交直线相切的半径为r的圆

直线向上和向下平移r后得到lup和ldw

每两条直线的交点即为圆心 并存入ans中

*/

int LLgetC(L l1,L l2,double r,vector<P>& ans) {

    P v1=normal(l1.v), v2=normal(l2.v);

    v1=v1/lenP(v1)*r, v2=v2/lenP(v2)*r;

    L l1up(l1.p+v1,l1.v), l1dw(l1.p-v1,l1.v);

    L l2up(l2.p+v2,l2.v), l2dw(l2.p-v2,l2.v);

    ans.pb(ins(l1up,l2up));

    ans.pb(ins(l1up,l2dw));

    ans.pb(ins(l1dw,l2up));

    ans.pb(ins(l1dw,l2dw));

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

    return ans.size();

}

/*求圆c1与c2的公切线

重合无数条 内离则没有

内切有一条 相交有两条

外切有三条 外离有四条

返回切线的数量 切点存入

*/

int CCgetL(C c1,C c2,vector <P>& ansa,vector <P>& ansb) {

    if(c1.r<c2.r) swap(c1,c2), swap(ansa,ansb);

    P v=c2.p-c1.p;

    double d2=(v).dot(v); // 圆心距的平方

    double base=angle(v);

    double rd=c1.r-c2.r; // 内切时的圆心距

    double rs=c1.r+c2.r; // 外切时的圆心距

    if(d2<rd*rd) return ; // 内离

    if(d2== && c1.r==c2.r) return -; // 重合

    if(d2==rd*rd) {

        ansa.pb(c1.acP(base)), ansb.pb(c2.acP(base));

        return ;

    } // 内切

    double ang=acos(rd/sqrt(d2)); // 外公切线与两圆心连线的夹角

    ansa.pb(c1.acP(base+ang)); ansb.pb(c2.acP(base+ang));

    ansa.pb(c1.acP(base-ang)); ansb.pb(c2.acP(base-ang));

    // 两条外切线

    if(d2==rs*rs) {

        ansa.pb(c1.acP(base)); ansb.pb(c2.acP(base));

    } // 外切

    else if(d2>rs*rs) {

        ang=acos(rs/sqrt(d2)); // 内公切线与两圆心连线的夹角

        ansa.pb(c1.acP(base+ang)); ansb.pb(c2.acP(base+ang));

        ansa.pb(c1.acP(base+ang)); ansb.pb(c2.acP(base+ang));

    } // 外离

    return ansa.size();

}

/*求圆c1与c2的面积交

S扇形 = r*r*ang  = r*l (l为弧长 l=ang*r)

S三角形 = r*r*sin(ang)*cos = r*r*0.5*sin(2*ang) = 0.5*r*h

S = S扇形 - S三角形 (对应圆弧的半边)

*/

double insAreaCC(P c1, double r1, P c2, double r2) {

    double a = lenP(c1-c2), b = r1, c = r2;

    double minr = min(r1,r2);

    if(r1+r2-a<eps) return ; // 两圆相离

    if(a-abs(r1-r2)<eps || abs(a)<eps)

        return PI*minr*minr; // 两圆包含

    double cosA=(a * a + b * b - c * c) / 2.0 / (a * b);

    double cosB=(a * a + c * c - b * b) / 2.0 / (a * c);

    double angA = acos(cosA), angB = acos(cosB);

    double s1 = r1*r1*angA - r1*r1*sin(angA)*cosA;

    double s2 = r2*r2*angB - r2*r2*sin(angB)*cosB;

    return s1 + s2;

}

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

void ops3(P p,C c) {

    vector <P> Lp; Lp.clear();

    int m=PCgetL(p,c,Lp); /// 得到切线向量

    vector <double> ans; ans.clear();

    for(int i=;i<m;i++) {

        double ang=angle(Lp[i]); /// 切线向量转为极角

        if(ang<) ang+=PI;

        if(abs(ang-PI)<eps) ang-=PI;

        ans.pb(ang);

    }

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

    printf("[");

    for(int i=;i<m;i++){

        if(i!=) printf(",");

        printf("%.6f",ans[i]*/PI); /// 极角转为角度

    }

    printf("]\n");

}

void ops4(P p,L l,double r) {

    vector <P> ans; ans.clear();

    int m=PLgetC(p,l,r,ans);

    printf("[");

    for(int i=;i<m;i++)

    {

        if(i!=) printf(",");

        printf("(%.6lf,%.6lf)",ans[i].x,ans[i].y);

    }

    printf("]\n");

}

void ops5(L l1,L l2,double r) {

    vector <P> ans; ans.clear();

    int m=LLgetC(l1,l2,r,ans);

    printf("[");

    for(int i=;i<m;i++) {

        if(i!=) printf(",");

        printf("(%.6lf,%.6lf)",ans[i].x,ans[i].y);

    }

    printf("]\n");

}

void ops6(C c1,C c2,double r)

{

    c1.r+=r, c2.r+=r;

    vector <P> ans; ans.clear();

    insCC(c1,c2,ans);

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

    printf("[");

    for(int i=;i<ans.size();i++) {

        if(i!=) printf(",");

        printf("(%.6lf,%.6lf)",ans[i].x,ans[i].y);

    }

    printf("]\n");

}

int main()

{

    string op;

    while(cin>>op) {

        if(op=="CircumscribedCircle") {

            P p1,p2,p3;

            p1.read(), p2.read(), p3.read();

            C c=csC(p1,p2,p3);

            printf("(%.6f,%.6f,%.6f)\n",c.p.x,c.p.y,c.r);

        }

        else if(op=="InscribedCircle") {

            P p1,p2,p3;

            p1.read(), p2.read(), p3.read();

            C c=isC(p1,p2,p3);

            printf("(%.6f,%.6f,%.6f)\n",c.p.x,c.p.y,c.r);

        }

        else if(op=="TangentLineThroughPoint") {

            C c; c.read();

            P p; p.read();

            ops3(p,c);

        }

        else if(op=="CircleThroughAPointAndTangentToALineWithRadius") {

            P p; P a,b;

            p.read(), a.read(), b.read();

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

            ops4(p,L(a,b-a),r);

        }

        else if(op=="CircleTangentToTwoLinesWithRadius") {

            P a,b; P c,d;

            a.read(), b.read();

            c.read(), d.read();

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

            ops5(L(a,b-a),L(c,c-d),r);

        }

        else { //if(op=="CircleTangentToTwoDisjointCirclesWithRadius") {

            C c1, c2;

            c1.read(), c2.read();

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

            ops6(c1,c2,r);

        }

    }

    return ;

}

随机增量法O(n)求最小圆覆盖

https://www.luogu.org/problemnew/solution/P1742

#include<bits/stdc++.h>

using namespace std;

#define LL long long

#define INF 0x3f3f3f3f

#define LLINF 0x3f3f3f3f3f3f3f3fLL

#define inc(i,j,k) for(int i=j;i<=k;i++)

#define dec(i,j,k) for(int i=j;i>=k;i--)

#define mem(i,j) memset(i,j,sizeof(i))

#define bug(args...) cout<<#args<<"="<<args<<endl;

const int N=1e5+;

const double eps=1e-;

struct P {

    double x,y;

    P(){} P(double x,double y):x(x),y(y){}

    P operator - (P p) { return P(x-p.x,y-p.y); }

    P operator + (P p) { return P(x+p.x,y+p.y); }

    P operator / (double d) { return P(x/d,y/d); }

    P operator * (double d) { return P(x*d,y*d); }

    double dot(P p) { return x*p.x+y*p.y; }

    double det(P p) { return x*p.y-y*p.x; }

};

struct C {

    P p; double r;

    C(){} C(P p,double r):p(p),r(r){}

};

double len(P p) { return sqrt(p.dot(p)); }

double len2(P p) { return p.dot(p); }

/*求三角形的外接圆（圆心、半径）*/

C csC(P a,P b,P c) {

    double bx=b.x-a.x, by=b.y-a.y;

    double cx=c.x-a.x, cy=c.y-a.y;

    double d=*(cy*bx-cx*by);

    double x=(cy*(bx*bx+by*by)-by*(cx*cx+cy*cy))/d+a.x;

    double y=(bx*(cx*cx+cy*cy)-cx*(bx*bx+by*by))/d+a.y;

    P r(x,y);

    return C(r,len(a-r));

}

/*求n个点的最小圆覆盖（圆心、半径）*/

C MCC() {

    C c=C(P(0.0,0.0),0.0);

    inc(i,,n) if(len2(p[i]-c.p)>c.r) {

        c=C(p[i],0.0);

        inc(j,,i-) if(len2(p[j]-c.p)>c.r) {

            c.p=(p[i]+p[j])/,c.r=len2(p[j]-c.p);

            inc(k,,j-) if(len2(p[k]-c.p)>c.r)

                c=csC(p[i],p[j],p[k]), c.r=len2(p[k]-c.p);

        }

    }

    c.r=sqrt(c.r);

    return c;

}

int n;

P p[N];

int main()

{

    while(~scanf("%d",&n)) {

        inc(i,,n) scanf("%lf%lf",&p[i].x,&p[i].y);

        random_shuffle(p+,p++n);

        C c=MCC();

        printf("%.10f\n%.10f %.10f\n",c.r,c.p.x,c.p.y);

    }

    return ;

}

巴特西

UVA 12304 /// 圆的综合题圆的模板

随机增量法O(n)求最小圆覆盖

最新文章

热门文章

巴特西

UVA 12304 /// 圆的综合题 圆的模板

随机增量法O(n)求最小圆覆盖

最新文章

热门文章

UVA 12304 /// 圆的综合题圆的模板