题目链接:https://cn.vjudge.net/problem/UVA-12304
题意:
作为题目大合集,有以下一些要求:
①给出三角形三个点,求三角形外接圆,求外接圆的圆心和半径。
②给出三角形三个点,求三角形内接圆,求内接圆的圆心和半径。
③给出一个圆,和一个点,求过该点的圆的切线与x轴的夹角(0<=angle<180);
④给出一条直线,一个点p,指定半径r,求经过点p的与直线相切的半径为r的圆;
⑤给出两条直线,求与这两条直线相切的圆;
⑥给出两个圆,求同时与这两个圆相切的圆;
题解:
综合运用平面几何模板即可。
AC代码:
#include<bits/stdc++.h> using namespace std; //--------------------------------------计算几何模板 - st-------------------------------------- const double eps = 1e-6; struct Point{ double x,y; Point(double tx=0,double ty=0):x(tx),y(ty){} }; typedef Point Vctor; //向量的加减乘除 Vctor operator + (Vctor A,Vctor B){return Vctor(A.x+B.x,A.y+B.y);} Vctor operator - (Point A,Point B){return Vctor(A.x-B.x,A.y-B.y);} Vctor operator * (Vctor A,double p){return Vctor(A.x*p,A.y*p);} Vctor operator / (Vctor A,double p){return Vctor(A.x/p,A.y/p);} bool operator < (Point A,Point B){return A.x < B.x || (A.x == B.x && A.y < B.y);} struct Line{ Point p; Vctor v; Line(Point p=Point(0,0),Vctor v=Vctor(0,0)):p(p),v(v){} Point point(double t){return p + v*t;} //获得直线上的距离p点t个单位长度的点 }; struct Circle{ Point c; double r; Circle(Point tc=Point(0,0),double tr=0):c(tc),r(tr){} Point point(double a){return Point( c.x + cos(a)*r , c.y + sin(a)*r);} }; int dcmp(double x) { if(fabs(x)<eps) return 0; else return (x<0)?(-1):(1); } bool operator == (Point A,Point B){return dcmp(A.x-B.x)==0 && dcmp(A.y-B.y)==0;} //向量的点积,长度,夹角 double Dot(Vctor A,Vctor B){return A.x*B.x+A.y*B.y;} double Length(Vctor A){return sqrt(Dot(A,A));} double Angle(Vctor A,Vctor B){return acos(Dot(A,B)/Length(A)/Length(B));} //叉积,三角形面积 double Cross(Vctor A,Vctor B){return A.x*B.y-A.y*B.x;} double TriangleArea(Point A,Point B,Point C){return Cross(B-A,C-A);} //向量的旋转,求向量的单位法线(即左转90度,然后长度归一) Vctor Rotate(Vctor A,double rad){return Vctor( A.x*cos(rad) - A.y*sin(rad) , A.x*sin(rad) + A.y*cos(rad) );} Vctor Normal(Vctor A) { double L = Length(A); return Vctor(-A.y/L, A.x/L); } //直线的交点 Point getLineIntersection(Line L1,Line L2) { Vctor u = L1.p-L2.p; double t = Cross(L2.v,u)/Cross(L1.v,L2.v); return L1.p + L1.v*t; } //点到直线的距离 double DistanceToLine(Point P,Line L) { return fabs(Cross(P-L.p,L.v))/Length(L.v); } //点到线段的距离 double DistanceToSegment(Point P,Point A,Point B) { if(A==B) return Length(P-A); Vctor v1 = B-A, v2 = P-A, v3 = P-B; if (dcmp(Dot(v1,v2)) < 0) return Length(v2); else if (dcmp(Dot(v1,v3)) > 0) return Length(v3); else return fabs(Cross(v1,v2))/Length(v1); } //点到直线的映射 Point getLineProjection(Point P,Line L) { return L.v + L.v*Dot(L.v,P-L.p)/Dot(L.v,L.v); } //判断线段是否规范相交 bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2) { double c1 = Cross(a2 - a1,b1 - a1), c2 = Cross(a2 - a1,b2 - a1), c3 = Cross(b2 - b1,a1 - b1), c4 = Cross(b2 - b1,a2 - b1); return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0; } //判断点是否在一条线段上 bool OnSegment(Point P,Point a1,Point a2) { return dcmp(Cross(a1 - P,a2 - P))==0 && dcmp(Dot(a1 - P,a2 - P))<0; } //多边形面积 double PolgonArea(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; } //判断圆与直线是否相交以及求出交点 int getLineCircleIntersection(Line L,Circle C,vector<Point> &sol) { double t1,t2; double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y; double e = a*a + c*c , f = 2*(a*b + c*d), g = b*b + d*d - C.r*C.r; double delta = f*f - 4.0*e*g; if(dcmp(delta)<0) return 0; else if(dcmp(delta)==0) { t1 = t2 = -f/(2.0*e); sol.push_back(L.point(t1)); return 1; } else { t1 = (-f-sqrt(delta))/(2.0*e); sol.push_back(L.point(t1)); t2 = (-f+sqrt(delta))/(2.0*e); sol.push_back(L.point(t2)); return 2; } } //判断并求出两圆的交点 double angle(Vctor v){return atan2(v.y,v.x);} int getCircleIntersection(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; //包含关系 } //圆心不重合 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), p2 = C1.point(a + da); sol.push_back(p1); if(p1==p2) return 1; sol.push_back(p2); return 2; } //求点到圆的切线 int getTangents(Point p,Circle C,vector<Line> &sol) { Vctor u=C.c-p; double dis=Length(u); if(dis<C.r) return 0; else if(dcmp(dis-C.r) == 0) { sol.push_back(Line(p,Rotate(u,M_PI/2))); return 1; } else { double ang=asin(C.r/dis); sol.push_back(Line(p,Rotate(u,-ang))); sol.push_back(Line(p,Rotate(u,ang))); return 2; } } //求两圆的切线 int getCircleTangents(Circle A,Circle B,Point *a,Point *b) { int cnt = 0; if(A.r<B.r){swap(A,B);swap(a,b);} //圆心距的平方 double 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); double rdiff = A.r - B.r; double rsum = A.r + B.r; double base = angle(B.c - A.c); //重合有无限多条 if(d2 == 0 && dcmp(A.r - B.r) == 0) return -1; //内切 if(dcmp(d2-rdiff*rdiff) == 0) { 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(dcmp(d2-rsum*rsum) == 0) { a[cnt] = A.point(base); b[cnt] = B.point(M_PI + base); cnt++; }//两条内切线 else if(dcmp(d2-rsum*rsum) > 0) { 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++; } return cnt; } //--------------------------------------计算几何模板 - ed-------------------------------------- Circle CircumscribedCircle(Point p1,Point p2,Point p3) //求外切圆,三点不能共线 { double up,down,x,y,r; double& x1=p1.x, x2=p2.x, x3=p3.x; double& y1=p1.y, y2=p2.y, y3=p3.y; up = (pow(x1,2)-pow(x2,2) + pow(y1,2)-pow(y2,2))*(y1-y3) - (pow(x1,2)-pow(x3,2) + pow(y1,2)-pow(y3,2))*(y1-y2); down = 2*(y1-y3)*(x1-x2) - 2*(y1-y2)*(x1-x3); x = up/down; up = (pow(x1,2)-pow(x2,2) + pow(y1,2)-pow(y2,2))*(x1-x3) - (pow(x1,2)-pow(x3,2) + pow(y1,2)-pow(y3,2))*(x1-x2); down = 2*(y1-y2)*(x1-x3) - 2*(y1-y3)*(x1-x2); y = up/down; r = sqrt( pow(x1-x,2)+pow(y1-y,2) ); return Circle(Point(x,y),r); } Circle InscribedCircle(Point p1,Point p2,Point p3) //求内切圆,三点不能共线 { double a,b,c,x,y,r; double& x1=p1.x, x2=p2.x, x3=p3.x; double& y1=p1.y, y2=p2.y, y3=p3.y; a = sqrt( pow(x2-x3,2) + pow(y2-y3,2) ); b = sqrt( pow(x3-x1,2) + pow(y3-y1,2) ); c = sqrt( pow(x1-x2,2) + pow(y1-y2,2) ); x = ( a*x1 + b*x2 + c*x3 )/( a+b+c ); y = ( a*y1 + b*y2 + c*y3 )/( a+b+c ); double p = (a+b+c)/2; r = sqrt( (p-a)*(p-b)*(p-c)/p ); return Circle(Point(x,y),r); } bool Line_cmp(Line a,Line b){return a.v<b.v;} void TangentLineThroughPoint(Circle C,Point p) { vector<Line> Lines; int cnt=getTangents(p,C,Lines); vector<double> ans; for(int i=0;i<cnt;i++) { double ang=angle(Lines[i].v); if(ang<0) ang+=M_PI; if(!dcmp(ang-M_PI)) ang-=M_PI; ans.push_back(ang); } sort(ans.begin(),ans.end()); printf("["); for(int i=0;i<ans.size();i++) { if(i!=0) printf(","); printf("%lf",180*ans[i]/M_PI); } printf("]\n"); } void CircleThroughAPointAndTangentToALineWithRadius(Point p,Point d1,Point d2,double r) { Vctor normal=Normal(d2-d1); normal=normal/Length(normal)*r; Line l1=Line(d1+normal,d2-d1), l2=Line(d1-normal,d2-d1); vector<Point> ans; getLineCircleIntersection(l1,Circle(p,r),ans); getLineCircleIntersection(l2,Circle(p,r),ans); sort(ans.begin(),ans.end()); printf("["); for(int i=0;i<ans.size();i++) { if(i!=0) printf(","); printf("(%.6lf,%.6lf)",ans[i].x,ans[i].y); } printf("]\n"); } void CircleTangentToTwoLinesWithRadius(Line L1,Line L2,double r) { Vctor normal1=Normal(L1.v), normal2=Normal(L2.v); normal1=normal1/Length(normal1)*r; normal2=normal2/Length(normal2)*r; Line L1_a=Line(L1.p+normal1,L1.v); Line L1_b=Line(L1.p-normal1,L1.v); Line L2_a=Line(L2.p+normal2,L2.v); Line L2_b=Line(L2.p-normal2,L2.v); vector<Point> ans; ans.push_back(getLineIntersection(L1_a,L2_a)); ans.push_back(getLineIntersection(L1_a,L2_b)); ans.push_back(getLineIntersection(L1_b,L2_a)); ans.push_back(getLineIntersection(L1_b,L2_b)); sort(ans.begin(),ans.end()); printf("["); for(int i=0;i<ans.size();i++) { if(i!=0) printf(","); printf("(%.6lf,%.6lf)",ans[i].x,ans[i].y); } printf("]\n"); } void CircleTangentToTwoDisjointCirclesWithRadius(Circle C1,Circle C2,double r) { C1.r+=r, C2.r+=r; vector<Point> ans; getCircleIntersection(C1,C2,ans); sort(ans.begin(),ans.end()); printf("["); for(int i=0;i<ans.size();i++) { if(i!=0) printf(","); printf("(%.6lf,%.6lf)",ans[i].x,ans[i].y); } printf("]\n"); } int main() { string input; while(cin>>input) { if(input=="CircumscribedCircle") { Point p1,p2,p3; cin>>p1.x>>p1.y>>p2.x>>p2.y>>p3.x>>p3.y; Circle ans=CircumscribedCircle(p1,p2,p3); printf("(%.6lf,%.6lf,%.6lf)\n",ans.c.x,ans.c.y,ans.r); } else if(input=="InscribedCircle") { Point p1,p2,p3; cin>>p1.x>>p1.y>>p2.x>>p2.y>>p3.x>>p3.y; Circle ans=InscribedCircle(p1,p2,p3); printf("(%.6lf,%.6lf,%.6lf)\n",ans.c.x,ans.c.y,ans.r); } else if(input=="TangentLineThroughPoint") { Circle C; Point p; cin>>C.c.x>>C.c.y>>C.r>>p.x>>p.y; TangentLineThroughPoint(C,p); } else if(input=="CircleThroughAPointAndTangentToALineWithRadius") { Point d1,d2; Point p; double r; cin>>p.x>>p.y>>d1.x>>d1.y>>d2.x>>d2.y>>r; CircleThroughAPointAndTangentToALineWithRadius(p,d1,d2,r); } else if(input=="CircleTangentToTwoLinesWithRadius") { Point p1,p2,p3,p4; double r; cin>>p1.x>>p1.y>>p2.x>>p2.y>>p3.x>>p3.y>>p4.x>>p4.y>>r; CircleTangentToTwoLinesWithRadius(Line(p1,(p2-p1)),Line(p3,(p4-p3)),r); } else //if(input=="CircleTangentToTwoDisjointCirclesWithRadius") { Circle C1,C2; double r; cin>>C1.c.x>>C1.c.y>>C1.r>>C2.c.x>>C2.c.y>>C2.r>>r; CircleTangentToTwoDisjointCirclesWithRadius(C1,C2,r); } } }