就是给了六个关于圆的算法。实现它们。
注意的是，不仅输出格式那个符号什么的要一样。坐标的顺序也要从小到大……
基本上没考虑什么精度的问题，然后就过了。
大白鼠又骗人。也许我的方法比較好？
我的做法就是列方程+旋转+平移
我的代码：
#include<iostream> #include<map> #include<string> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<queue> #include<vector> #include<algorithm> using namespace std; const double eps=1e-7; const double pi=acos(-1.0); int dcmp(double x){return fabs(x)<eps?0:x<0?-1:1;} struct dot { double x,y; dot(){} dot(double a,double b){x=a;y=b;} dot operator +(dot a){return dot(x+a.x,y+a.y);} dot operator -(dot a){return dot(x-a.x,y-a.y);} dot operator *(double a){return dot(x*a,y*a);} double operator *(dot a){return x*a.y-y*a.x;} dot operator /(double a){return dot(x/a,y/a);} double operator /(dot a){return x*a.x+y*a.y;} bool operator ==(dot a){return x==a.x&&y==a.y;} void in(){scanf("%lf%lf",&x,&y);} void out(){printf("%f %f\n",x,y);} dot norv(){return dot(-y,x);} dot univ(){double a=mod();return dot(x/a,y/a);} dot ro(double a){return dot(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a));} double mod(){return sqrt(x*x+y*y);} double dis(dot a){return sqrt(pow(x-a.x,2)+pow(y-a.y,2));} }; bool operator >(dot a,dot b) { return dcmp(a.x-b.x)!=0?a.x>b.x:a.y>b.y; } struct fun { double a,b,c; fun(){} fun(double x,double y,double z){a=x;b=y;c=z;} fun(dot d,dot e){a=e.y-d.y;b=d.x-e.x;c=d.x*e.y-d.y*e.x;} dot sf(fun d) { double e,f,g; e=dot(a,d.a)*dot(b,d.b); f=dot(c,d.c)*dot(b,d.b); g=dot(a,d.a)*dot(c,d.c); return dot(f/e,g/e); } void in(){scanf("%lf%lf%lf",&a,&b,&c);} void out(){printf("%f %f %f\n",a,b,c);} }; void solve1(dot a,dot b,dot c) { dot g; fun e,f; double r; e=fun((a+b)/2,(a+b)/2+(a-b).norv()); f=fun((a+c)/2,(a+c)/2+(a-c).norv()); g=e.sf(f); r=g.dis(a); printf("(%.6lf,%.6lf,%.6lf)\n",g.x,g.y,r); } void solve2(dot a,dot b,dot c) { double e,d,f,g,r; fun h,i; dot j; d=a.dis(b); e=a.dis(c); f=b.dis(c); g=acos((d*d+e*e-f*f)/2/d/e)/2; if(dcmp((b-a)*(c-a))>0) h=fun(a,(b-a).ro(g)+a); else h=fun(a,(c-a).ro(g)+a); g=acos((e*e+f*f-d*d)/2/e/f)/2; if(dcmp((a-c)*(b-c))>0) i=fun(c,(a-c).ro(g)+c); else i=fun(c,(b-c).ro(g)+c); j=h.sf(i); r=fabs((j-a)*(b-a)/a.dis(b)); printf("(%.6lf,%.6lf,%.6lf)\n",j.x,j.y,r); } double cg(dot a) { double b=atan2(a.y,a.x); b=b/pi*180; return dcmp(b)<0?
b+180:dcmp(b-180)!=0?b:0; } void solve3(dot a,double r,dot p) { dot d,g; double b,c,e,f; b=a.dis(p); c=asin(r/b); if(dcmp(b-r)<0) printf("[]\n"); else if(dcmp(b-r)==0) { d=(p-a).norv(); e=cg(d); printf("[%.6f]\n",e); } else { d=(a-p).ro(c); g=(a-p).ro(2*pi-c); e=cg(d); f=cg(g); if(e>f)swap(e,f); printf("[%.6f,%.6f]\n",e,f); } } void solve4(dot p,dot a,dot b,double r) { double d,e; dot c,f,g; c=fun(a,b).sf(fun(p,p+(a-b).norv())); d=p.dis(c); if(dcmp(d-2*r)>0) printf("[]\n"); else if(dcmp(d)==0) { f=p+(a-b).norv().univ()*r; g=p-(a-b).norv().univ()*r; if(f>g)swap(f,g); printf("[(%.6f,%.6f),(%.6f,%.6f)]\n",f.x,f.y,g.x,g.y); } else if(dcmp(d-2*r)==0) { f=(p+c)/2; printf("[(%.6f,%.6f)]\n",f.x,f.y); } else { e=acos((d-r)/r); f=((c-p).univ()*r).ro(e)+p; e=-e; g=((c-p).univ()*r).ro(e)+p; if(f>g)swap(f,g); printf("[(%.6f,%.6f),(%.6f,%.6f)]\n",f.x,f.y,g.x,g.y); } } void solve5(dot a,dot b,dot c,dot d,double r) { dot i,j,k,l; double t1,t2; fun e,f,g,h; e=fun(a,b); f=fun(c,d); t1=sqrt(pow(e.a,2)+pow(e.b,2)); t2=sqrt(pow(f.a,2)+pow(f.b,2)); g=fun(e.a/t1,e.b/t1,e.c/t1+r); h=fun(f.a/t2,f.b/t2,f.c/t2+r); i=g.sf(h); g.c=e.c/t1-r;j=g.sf(h); h.c=f.c/t2-r;k=g.sf(h); g.c=e.c/t1+r;l=g.sf(h); if(i>j)swap(i,j); if(i>k)swap(i,k); if(i>l)swap(i,l); if(j>k)swap(j,k); if(j>l)swap(j,l); if(k>l)swap(k,l); printf("[(%.6f,%.6f),(%.6f,%.6f),(%.6f,%.6f),(%.6f,%.6f)]\n", i.x,i.y,j.x,j.y,k.x,k.y,l.x,l.y); } void solve6(dot a,double r1,dot b,double r2,double r) { dot f,g; double c,d,e,h; c=a.dis(b); d=r1+r; e=r2+r; if(dcmp(c-r-r-r1-r2)>0) printf("[]\n"); else if(dcmp(c-r-r-r1-r2)==0) { f=a+(b-a).univ()*(r1+r); printf("[(%.6f,%.6f)]\n",f.x,f.y); } else { h=acos((c*c+d*d-e*e)/2/c/d); f=((b-a).univ()*(r1+r)).ro(h)+a; h=-h; g=((b-a).univ()*(r1+r)).ro(h)+a; if(f>g)swap(f,g); printf("[(%.6f,%.6f),(%.6f,%.6f)]\n",f.x,f.y,g.x,g.y); } } int main() { char s[100]; dot a,b,c,d; double r,r1,r2; while(scanf("%s",s)!=EOF) { if(strcmp(s,"CircumscribedCircle")==0) { a.in();b.in();c.in(); solve1(a,b,c); } else if(strcmp(s,"InscribedCircle")==0) { a.in();b.in();c.in(); solve2(a,b,c); } else if(strcmp(s,"TangentLineThroughPoint")==0) { a.in();cin>>r;b.in(); solve3(a,r,b); } else if(strcmp(s,"CircleThroughAPointAndTangentToALineWithRadius")==0) { a.in();b.in();c.in();cin>>r; solve4(a,b,c,r); } else if(strcmp(s,"CircleTangentToTwoLinesWithRadius")==0) { a.in();b.in();c.in();d.in();cin>>r; solve5(a,b,c,d,r); } else { a.in();cin>>r1;b.in();cin>>r2;cin>>r; solve6(a,r1,b,r2,r); } } /*solve1(dot(0,0),dot(20,1),dot(8,17)); solve2(dot(0,0),dot(20,1),dot(8,17)); solve3(dot(200,200),100,dot(40,150)); solve3(dot(200,200),100,dot(200,100)); solve3(dot(200,200),100,dot(270,210)); solve4(dot(100,200),dot(75,190),dot(185,65),100); solve4(dot(75,190),dot(75,190),dot(185,65),100); solve4(dot(100,300),dot(100,100),dot(200,100),100); solve4(dot(100,300),dot(100,100),dot(200,100),99); solve5(dot(50,80),dot(320,190),dot(85,190),dot(125,40),30); solve6(dot(120,200),50,dot(210,150),30,25); solve6(dot(100,100),80,dot(300,250),70,50);*/ }
Description
This is a collection of 110 (in binary) 2D geometry problems.
CircumscribedCircle x1 y1 x2 y2 x3 y3Find out the circumscribed circle of triangle (x1,y1)-(x2,y2)-(x3,y3). These three points are guaranteed to be non-collinear. The circle is formatted as (x,y,r) where (x,y) is the center of circle, r is the radius.
InscribedCircle x1 y1 x2 y2 x3 y3Find out the inscribed circle of triangle (x1,y1)-(x2,y2)-(x3,y3). These three points are guaranteed to be non-collinear. The circle is formatted as (x,y,r) where (x,y) is the center of circle, r is the radius.
TangentLineThroughPoint xc yc r xp ypFind out the list of tangent lines of circle centered (xc,yc) with radius r that pass through point (xp,yp). Each tangent line is formatted as a single real number "angle" (in degrees), the angle of the line (0<=angle<180). Note that the answer should be formatted as a list (see below for details).
CircleThroughAPointAndTangentToALineWithRadius xp yp x1 y1 x2 y2 rFind out the list of circles passing through point (xp, yp) that is tangent to a line (x1,y1)-(x2,y2) with radius r. Each circle is formatted as (x,y), since the radius is already given. Note that the answer should be formatted as a list. If there is no answer, you should print an empty list.
CircleTangentToTwoLinesWithRadius x1 y1 x2 y2 x3 y3 x4 y4 rFind out the list of circles tangent to two non-parallel lines (x1,y1)-(x2,y2) and (x3,y3)-(x4,y4), having radius r. Each circle is formatted as (x,y), since the radius is already given. Note that the answer should be formatted as a list. If there is no answer, you should print an empty list.
CircleTangentToTwoDisjointCirclesWithRadius x1 y1 r1 x2 y2 r2 rFind out the list of circles externally tangent to two disjoint circles (x1,y1,r1) and (x2,y2,r2), having radius r. By "externally" we mean it should not enclose the two given circles. Each circle is formatted as (x,y), since the radius is already given. Note that the answer should be formatted as a list. If there is no answer, you should print an empty list.
For each line described above, the two endpoints will not be equal. When formatting a list of real numbers, the numbers should be sorted in increasing order; when formatting a list of (x,y) pairs, the pairs should be sorted in increasing order of x. In case of tie, smaller y comes first.
There will be at most 1000 sub-problems, one in each line, formatted as above. The coordinates will be integers with absolute value not greater than 1000. The input is terminated by end of file (EOF).
For each input line, print out your answer formatted as stated in the problem description. Each number in the output should be rounded to six digits after the decimal point. Note that the list should be enclosed by square brackets, and tuples should be enclosed by brackets. There should be no space characters in each line of your output.
Source
Root :: Prominent Problemsetters :: Rujia Liu Root :: Rujia Liu's Presents :: Present 4: Dedicated to Geometry and CG Lovers Root :: AOAPC I: Beginning Algorithm Contests -- Training Guide (Rujia Liu) :: Chapter 4. Geometry :: Geometric Computations in 2D :: Examples转载于:https://www.cnblogs.com/bhlsheji/p/5407160.html
相关资源：数据结构—成绩单生成器