题意：要求解答6个关于圆的问题。
1.给出三角形坐标求外接圆 2.给出三角形坐标求内切圆 3.给出一个圆心和半径已知的圆，求过点(x,y)的所有和这个圆相切的直线 4.求所有和已知直线相切的过定点(x,y)的已知半径的圆的圆心 5.给出两个不平行的直线，求所有半径为r的同时和这两个直线相切的圆 6.给定两个相离的圆，求出所有和这两个圆外切的半径为r的圆。比较恶心的计算几何模板题，直接模板吧。。。。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #define clc(a,b) memset(a,b,sizeof(a)) 10 #define LL long long int 11 #define up(i,x,y) for(i=x;i<=y;i++) 12 #define w(a) while(a) 13 using namespace std; 14 const int inf=0x3f3f3f3f; 15 const int N = 110; 16 const int maxn = 50; 17 const double eps = 1e-10; //调到1e-6以上第4问就可以用delta判断切线,但《训练指南》建议，尽量不要调eps 18 const double pi = acos(-1); 19 20 char type[maxn]; 21 22 int dcmp(double x) 23 { 24 return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1); 25 } 26 27 struct Point 28 { 29 double x; 30 double y; 31 32 Point(double x = 0, double y = 0):x(x), y(y) {} 33 34 bool operator < (const Point& e) const 35 { 36 return dcmp(x - e.x) < 0 || (dcmp(x - e.x) == 0 && dcmp(y - e.y) < 0); 37 } 38 39 bool operator == (const Point& e) const 40 { 41 return dcmp(x - e.x) == 0 && dcmp(y - e.y) == 0; 42 } 43 44 int read() 45 { 46 return scanf("%lf%lf", &x, &y); 47 } 48 } p[3]; 49 50 typedef Point Vector; 51 52 Vector operator + (Point A, Point B) 53 { 54 return Vector(A.x + B.x, A.y + B.y); 55 } 56 57 Vector operator - (Point A, Point B) 58 { 59 return Vector(A.x - B.x, A.y - B.y); 60 } 61 62 Vector operator * (Point A, double p) 63 { 64 return Vector(A.x * p, A.y * p); 65 } 66 67 Vector operator / (Point A, double p) 68 { 69 return Vector(A.x / p, A.y / p); 70 } 71 72 struct Line 73 { 74 Point p; 75 Point v; 76 77 Line() {} 78 Line(Point p, Point v):p(p), v(v) {} 79 80 int read() 81 { 82 return scanf("%lf%lf%lf%lf", &p.x, &p.y, &v.x, &v.y); 83 } 84 85 Point point(double t) 86 { 87 return p + v * t; 88 } 89 }; 90 91 struct Circle 92 { 93 Point c; 94 double r; 95 96 Circle() {} 97 Circle(Point c, double r):c(c), r(r) {} 98 99 int read()100 {101 return scanf("%lf%lf%lf", &c.x, &c.y, &r);102 }103 104 Point point(double a)105 {106 return Point(c.x + r * cos(a), c.y + r * sin(a));107 }108 };109 110 double Dot(Vector A, Vector B)111 {112 return A.x * B.x + A.y * B.y;113 }114 115 double Cross(Vector A, Vector B)116 {117 return A.x * B.y - B.x * A.y;118 }119 120 double Length(Vector A)121 {122 return sqrt(Dot(A, A));123 }124 125 Vector Rotate(Vector A, double rad)126 {127 return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));128 }129 130 Vector Normal(Vector A)131 {132 double L = Length(A);133 return Vector(-A.y / L, A.x / L);134 }135 136 double DistanceToLine(Point P, Point A, Point B) //点到直线的距离137 {138 Vector v1 = B - A;139 Vector v2 = P - A;140 return fabs(Cross(v1, v2) / Length(v1));141 }142 143 double angle(Vector v) //求向量的极角144 {145 return atan2(v.y, v.x);146 }147 148 Point GetLineIntersection(Line l1, Line l2) //求两直线的交点（前提：相交）149 {150 Vector u = l1.p - l2.p;151 double t = Cross(l2.v, u) / Cross(l1.v, l2.v);152 return l1.point(t);153 }154 155 int getLineCircleIntersection(Line l, Circle C, double& t1, double& t2, vector & sol) //求直线与圆的交点156 {157 double a = l.v.x;158 double b = l.p.x - C.c.x;159 double c = l.v.y;160 double d = l.p.y - C.c.y;161 double e = a * a + c * c;162 double f = 2 * (a * b + c * d);163 double g = b * b + d * d - C.r * C.r;164 double delta = f * f - 4 * e * g;165 double dist = DistanceToLine(C.c, l.p, l.p+l.v);166 if(dcmp(dist - C.r) == 0) //相切，此处需特殊判断，不能用delta167 {168 t1 = t2 = -f / (2 * e);169 sol.push_back(l.point(t1));170 return 1;171 }172 if(dcmp(delta) < 0) return 0; //相离173 else //相交174 {175 t1 = (-f - sqrt(delta)) / (2 * e);176 sol.push_back(l.point(t1));177 t2 = (-f + sqrt(delta)) / (2 * e);178 sol.push_back(l.point(t2));179 return 2;180 }181 }182 183 int GetCircleCircleIntersection(Circle C1, Circle C2, vector & sol) //求圆与圆的交点184 {185 double d = Length(C1.c - C2.c);186 if(dcmp(d) == 0)187 {188 if(dcmp(C1.r - C2.r) == 0) return -1; //两圆重合189 return 0; //同心圆但不重合190 }191 if(dcmp(C1.r + C2.r - d) < 0) return 0; //外离192 if(dcmp(fabs(C1.r - C2.r) - d) > 0) return 0; //内含193 double a = angle(C2.c - C1.c);194 double da = acos((C1.r * C1.r + d * d - C2.r * C2.r) / (2 * C1.r * d));195 Point p1 = C1.point(a + da);196 Point p2 = C1.point(a - da);197 sol.push_back(p1);198 if(p1 == p2) return 1; //外切199 sol.push_back(p2);200 return 2;201 }202 203 Circle CircumscribedCircle(Point p1, Point p2, Point p3) //求三角形的外心204 {205 double Bx = p2.x - p1.x, By = p2.y - p1.y;206 double Cx = p3.x - p1.x, Cy = p3.y - p1.y;207 double D = 2 * (Bx * Cy - By * Cx);208 double cx = (Cy * (Bx * Bx + By * By) - By * (Cx * Cx + Cy * Cy)) / D + p1.x;209 double cy = (Bx * (Cx * Cx + Cy * Cy) - Cx * (Bx * Bx + By * By)) / D + p1.y;210 Point p(cx, cy);211 return Circle(p, Length(p1-p));212 }213 214 Circle InscribedCircle(Point p1, Point p2, Point p3) //求三角形的内切圆215 {216 double a = Length(p3 - p2);217 double b = Length(p3 - p1);218 double c = Length(p2 - p1);219 Point p = (p1 * a + p2 * b + p3 * c) / (a + b + c);220 return Circle(p, DistanceToLine(p, p2, p3));221 }222 223 int TangentLineThroughPoint(Point p, Circle C, Vector *v) //求点到圆的直线224 {225 Vector u = C.c - p;226 double dist = Length(u);227 if(dcmp(dist - C.r) < 0) return 0;228 else if(dcmp(dist - C.r) < eps)229 {230 v[0] = Rotate(u, pi / 2);231 return 1;232 }233 else234 {235 double ang = asin(C.r / dist);236 v[0] = Rotate(u, ang);237 v[1] = Rotate(u, -ang);238 return 2;239 }240 }241 242 void CircleThroughAPointAndTangentToALineWithRadius(Point p, Point p1, Point p2, double r)243 {244 Vector AB = p2 - p1;245 Vector change1 = Rotate(AB, pi / 2) / Length(AB) * r;246 Vector change2 = Rotate(AB, -pi / 2) / Length(AB) * r;247 Line l1(p1 + change1, AB);248 Line l2(p1 + change2, AB);249 vector sol;250 sol.clear();251 double t1, t2;252 int cnt1 = getLineCircleIntersection(l1, Circle(p, r), t1, t2, sol);253 int cnt2 = getLineCircleIntersection(l2, Circle(p, r), t1, t2, sol);254 int cnt = cnt1 + cnt2;255 if(cnt) sort(sol.begin(), sol.end());256 printf("[");257 for(int i = 0; i < cnt; i++)258 {259 printf("(%.6f,%.6f)", sol[i].x, sol[i].y);260 if(cnt == 2 && !i) printf(",");261 }262 puts("]");263 }264 265 void CircleTangentToTwoLinesWithRadius(Point A, Point B, Point C, Point D, double r)266 {267 Vector AB = B - A;268 Vector change = Normal(AB) * r;269 Point newA1 = A + change;270 Point newA2 = A - change;271 Vector CD = D - C;272 Vector update = Normal(CD) * r;273 Point newC1 = C + update;274 Point newC2 = C - update;275 Point p[5];276 p[0] = GetLineIntersection(Line(newA1, AB), Line(newC1, CD));277 p[1] = GetLineIntersection(Line(newA1, AB), Line(newC2, CD));278 p[2] = GetLineIntersection(Line(newA2, AB), Line(newC1, CD));279 p[3] = GetLineIntersection(Line(newA2, AB), Line(newC2, CD));280 sort(p, p + 4);281 printf("[");282 printf("(%.6f,%.6f)", p[0].x, p[0].y);283 for(int i = 1; i < 4; i++)284 {285 printf(",(%.6f,%.6f)", p[i].x, p[i].y);286 }287 puts("]");288 }289 290 void CircleTangentToTwoDisjointCirclesWithRadius(Circle C1, Circle C2, double r)291 {292 Vector CC = C2.c - C1.c;293 double rdist = Length(CC);294 if(dcmp(2 * r - rdist + C1.r + C2.r) < 0) puts("[]");295 else if(dcmp(2 * r - rdist + C1.r + C2.r) == 0)296 {297 double ang = angle(CC);298 Point A = C1.point(ang);299 Point B = C2.point(ang + pi);300 Point ret = (A + B) / 2;301 printf("[(%.6f,%.6f)]\n", ret.x, ret.y);302 }303 else304 {305 Circle A = Circle(C1.c, C1.r + r);306 Circle B = Circle(C2.c, C2.r + r);307 vector sol;308 sol.clear();309 GetCircleCircleIntersection(A, B, sol);310 sort(sol.begin(), sol.end());311 printf("[(%.6f,%.6f),(%.6f,%.6f)]\n", sol[0].x, sol[0].y, sol[1].x, sol[1].y);312 }313 }314 315 int main()316 {317 while(scanf("%s", type) == 1)318 {319 if(strcmp(type, "CircumscribedCircle") == 0)320 {321 Point p1, p2, p3;322 p1.read();323 p2.read();324 p3.read();325 Circle ret = CircumscribedCircle(p1, p2, p3);326 printf("(%f,%f,%f)\n", ret.c.x, ret.c.y, ret.r);327 }328 else if(strcmp(type, "InscribedCircle") == 0)329 {330 Point p1, p2, p3;331 p1.read();332 p2.read();333 p3.read();334 Circle ret = InscribedCircle(p1, p2, p3);335 printf("(%f,%f,%f)\n", ret.c.x, ret.c.y, ret.r);336 }337 else if(strcmp(type, "TangentLineThroughPoint") == 0)338 {339 Circle C;340 Point p;341 C.read();342 p.read();343 Vector v[3];344 int cnt = TangentLineThroughPoint(p, C, v);345 double ret[3];346 for(int i = 0; i < cnt; i++)347 {348 ret[i] = angle(v[i]);349 if(dcmp(ret[i] - pi) == 0) ret[i] = 0;350 if(dcmp(ret[i]) < 0) ret[i] += pi;351 }352 sort(ret, ret + cnt);353 printf("[");354 for(int i = 0; i < cnt; i++)355 {356 printf("%.6f", ret[i] / pi * 180);357 if(cnt == 2 && !i) printf(",");358 }359 puts("]");360 }361 else if(strcmp(type, "CircleThroughAPointAndTangentToALineWithRadius") == 0)362 {363 Point p, p1, p2;364 double r;365 p.read();366 p1.read();367 p2.read();368 scanf("%lf", &r);369 CircleThroughAPointAndTangentToALineWithRadius(p, p1, p2, r);370 }371 else if(strcmp(type, "CircleTangentToTwoLinesWithRadius") == 0)372 {373 Point A, B, C, D;374 double r;375 A.read();376 B.read();377 C.read();378 D.read();379 scanf("%lf", &r);380 CircleTangentToTwoLinesWithRadius(A, B, C, D, r);381 }382 else383 {384 Circle C1, C2;385 double r;386 C1.read();387 C2.read();388 scanf("%lf", &r);389 CircleTangentToTwoDisjointCirclesWithRadius(C1, C2, r);390 }391 }392 return 0;393 }