uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3726
新增加与圆有关的模板，过了这题。
使用模板的时候犯了一个小错误，忘记了自己的点到直线的距离是一个有向距离，结果就把自己坑了。
View Code
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <set> 5 #include <vector> 6 #include <iostream> 7 #include <algorithm> 8 9 using namespace std; 10 11 #define REP(i, n) for (int i = 0; i < (n); i++) 12 13 struct Point { 14 double x, y; 15 Point() {} 16 Point(double x, double y) : x(x), y(y) {} 17 } ; 18 template<class T> T sqr(T x) { return x * x;} 19 inline double ptDis(Point a, Point b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));} 20 21 // basic calculations 22 typedef Point Vec; 23 Vec operator + (Vec a, Vec b) { return Vec(a.x + b.x, a.y + b.y);} 24 Vec operator - (Vec a, Vec b) { return Vec(a.x - b.x, a.y - b.y);} 25 Vec operator * (Vec a, double p) { return Vec(a.x * p, a.y * p);} 26 Vec operator / (Vec a, double p) { return Vec(a.x / p, a.y / p);} 27 28 const double eps = 1e-8; 29 const double pi = acos(-1.0); 30 inline int sgn(double x) { return fabs(x) < eps ? 0 : (x < 0 ? -1 : 1);} 31 bool operator < (Point a, Point b) { return a.x < b.x || (a.x == b.x && a.y < b.y);} 32 bool operator == (Point a, Point b) { return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;} 33 34 inline double dotDet(Vec a, Vec b) { return a.x * b.x + a.y * b.y;} 35 inline double vecLen(Vec x) { return sqrt(sqr(x.x) + sqr(x.y));} 36 inline double angle(Vec v) { return atan2(v.y, v.x);} 37 inline double angle(Vec a, Vec b) { return acos(dotDet(a, b) / vecLen(a) / vecLen(b));} 38 inline double crossDet(Vec a, Vec b) { return a.x * b.y - a.y * b.x;} 39 inline double triArea(Point a, Point b, Point c) { return fabs(crossDet(b - a, c - a));} 40 inline Vec vecUnit(Vec x) { return x / vecLen(x);} 41 inline Vec rotate(Vec x, double rad) { return Vec(x.x * cos(rad) - x.y * sin(rad), x.x * sin(rad) + x.y * cos(rad));} 42 Vec normal(Vec x) { 43 double len = vecLen(x); 44 return Vec(- x.y / len, x.x / len); 45 } 46 47 struct Line { 48 Point s, t; 49 Line() {} 50 Line(Point s, Point t) : s(s), t(t) {} 51 Point point(double x) { 52 return s + (t - s) * x; 53 } 54 } ; 55 typedef Line Seg; 56 57 inline bool onSeg(Point x, Point a, Point b) { return sgn(crossDet(a - x, b - x)) == 0 && sgn(dotDet(a - x, b - x)) < 0;} 58 inline bool onSeg(Point x, Seg s) { return onSeg(x, s.s, s.t);} 59 60 // 0 : not intersect 61 // 1 : proper intersect 62 // 2 : improper intersect 63 int segIntersect(Point a, Point c, Point b, Point d) { 64 Vec v1 = b - a, v2 = c - b, v3 = d - c, v4 = a - d; 65 int a_bc = sgn(crossDet(v1, v2)); 66 int b_cd = sgn(crossDet(v2, v3)); 67 int c_da = sgn(crossDet(v3, v4)); 68 int d_ab = sgn(crossDet(v4, v1)); 69 if (a_bc * c_da > 0 && b_cd * d_ab > 0) return 1; 70 if (onSeg(b, a, c) && c_da) return 2; 71 if (onSeg(c, b, d) && d_ab) return 2; 72 if (onSeg(d, c, a) && a_bc) return 2; 73 if (onSeg(a, d, b) && b_cd) return 2; 74 return 0; 75 } 76 inline int segIntersect(Seg a, Seg b) { return segIntersect(a.s, a.t, b.s, b.t);} 77 78 // point of the intersection of 2 lines 79 Point lineIntersect(Point P, Vec v, Point Q, Vec w) { 80 Vec u = P - Q; 81 double t = crossDet(w, u) / crossDet(v, w); 82 return P + v * t; 83 } 84 inline Point lineIntersect(Line a, Line b) { return lineIntersect(a.s, a.t - a.s, b.s, b.t - b.s);} 85 86 // Warning: This is a DIRECTED Distance!!! 87 double pt2Line(Point x, Point a, Point b) { 88 Vec v1 = b - a, v2 = x - a; 89 return crossDet(v1, v2) / vecLen(v1); 90 } 91 inline double pt2Line(Point x, Line L) { return pt2Line(x, L.s, L.t);} 92 93 double pt2Seg(Point x, Point a, Point b) { 94 if (a == b) return vecLen(x - a); 95 Vec v1 = b - a, v2 = x - a, v3 = x - b; 96 if (sgn(dotDet(v1, v2)) < 0) return vecLen(v2); 97 if (sgn(dotDet(v1, v3)) > 0) return vecLen(v3); 98 return fabs(crossDet(v1, v2)) / vecLen(v1); 99 } 100 inline double pt2Seg(Point x, Seg s) { return pt2Seg(x, s.s, s.t);} 101 102 struct Poly { 103 vector<Point> pt; 104 Poly() {} 105 Poly(vector<Point> pt) : pt(pt) {} 106 double area() { 107 double ret = 0.0; 108 int sz = pt.size(); 109 for (int i = 1; i < sz; i++) { 110 ret += crossDet(pt[i], pt[i - 1]); 111 } 112 return fabs(ret / 2.0); 113 } 114 } ; 115 116 struct Circle { 117 Point c; 118 double r; 119 Circle(Point c, double r) : c(c), r(r) {} 120 Point point(double a) { 121 return Point(c.x + cos(a) * r, c.y + sin(a) * r); 122 } 123 } ; 124 125 int lineCircleIntersect(Line L, Circle C, double &t1, double &t2, vector<Point> &sol) { 126 double a = L.s.x, b = L.t.x - C.c.x, c = L.s.y, d = L.t.y - C.c.y; 127 double e = sqr(a) + sqr(c), f = 2 * (a * b + c * d), g = sqr(b) + sqr(d) - sqr(C.r); 128 double delta = sqr(f) - 4.0 * e * g; 129 if (sgn(delta) < 0) return 0; 130 if (sgn(delta) == 0) { 131 t1 = t2 = -f / (2.0 * e); 132 sol.push_back(L.point(t1)); 133 return 1; 134 } 135 t1 = (-f - sqrt(delta)) / (2.0 * e); 136 sol.push_back(L.point(t1)); 137 t2 = (-f + sqrt(delta)) / (2.0 * e); 138 sol.push_back(L.point(t2)); 139 return 2; 140 } 141 142 int lineCircleIntersect(Line L, Circle C, vector<Point> &sol) { 143 Vec dir = L.t - L.s, nor = normal(dir); 144 Point mid = lineIntersect(C.c, nor, L.s, dir); 145 double len = sqr(C.r) - sqr(ptDis(C.c, mid)); 146 if (sgn(len) < 0) return 0; 147 if (sgn(len) == 0) { 148 sol.push_back(mid); 149 return 1; 150 } 151 Vec dis = vecUnit(dir); 152 len = sqrt(len); 153 sol.push_back(mid + dis * len); 154 sol.push_back(mid - dis * len); 155 return 2; 156 } 157 158 // -1 : coincide 159 int circleCircleIntersect(Circle C1, Circle C2, vector<Point> &sol) { 160 double d = vecLen(C1.c - C2.c); 161 if (sgn(d) == 0) { 162 if (sgn(C1.r - C2.r) == 0) { 163 return -1; 164 } 165 return 0; 166 } 167 if (sgn(C1.r + C2.r - d) < 0) return 0; 168 if (sgn(fabs(C1.r - C2.r) - d) > 0) return 0; 169 double a = angle(C2.c - C1.c); 170 double da = acos((sqr(C1.r) + sqr(d) - sqr(C2.r)) / (2.0 * C1.r * d)); 171 Point p1 = C1.point(a - da), p2 = C1.point(a + da); 172 sol.push_back(p1); 173 if (p1 == p2) return 1; 174 sol.push_back(p2); 175 return 2; 176 } 177 178 int tangent(Point p, Circle C, vector<Vec> &sol) { 179 Vec u = C.c - p; 180 double dist = vecLen(u); 181 if (dist < C.r) return 0; 182 if (sgn(dist - C.r) == 0) { 183 sol.push_back(rotate(u, pi / 2.0)); 184 return 1; 185 } 186 double ang = asin(C.r / dist); 187 sol.push_back(rotate(u, -ang)); 188 sol.push_back(rotate(u, ang)); 189 return 2; 190 } 191 192 // ptA : points of tangency on circle A 193 // ptB : points of tangency on circle B 194 int tangent(Circle A, Circle B, vector<Point> &ptA, vector<Point> &ptB) { 195 if (A.r < B.r) { 196 swap(A, B); 197 swap(ptA, ptB); 198 } 199 int d2 = sqr(A.c.x - B.c.x) + sqr(A.c.y - B.c.y); 200 int rdiff = A.r - B.r, rsum = A.r + B.r; 201 if (d2 < sqr(rdiff)) return 0; 202 double base = atan2(B.c.y - A.c.y, B.c.x - A.c.x); 203 if (d2 == 0 && A.r == B.r) return -1; 204 if (d2 == sqr(rdiff)) { 205 ptA.push_back(A.point(base)); 206 ptB.push_back(B.point(base)); 207 return 1; 208 } 209 double ang = acos((A.r - B.r) / sqrt(d2)); 210 ptA.push_back(A.point(base + ang)); 211 ptB.push_back(B.point(base + ang)); 212 ptA.push_back(A.point(base - ang)); 213 ptB.push_back(B.point(base - ang)); 214 if (d2 == sqr(rsum)) { 215 ptA.push_back(A.point(base)); 216 ptB.push_back(B.point(pi + base)); 217 } else if (d2 > sqr(rsum)) { 218 ang = acos((A.r + B.r) / sqrt(d2)); 219 ptA.push_back(A.point(base + ang)); 220 ptB.push_back(B.point(pi + base + ang)); 221 ptA.push_back(A.point(base - ang)); 222 ptB.push_back(B.point(pi + base - ang)); 223 } 224 return (int) ptA.size(); 225 } 226 227 /****************** template above *******************/ 228 229 const char *str[6] = { "CircumscribedCircle", "InscribedCircle", "TangentLineThroughPoint", "CircleThroughAPointAndTangentToALineWithRadius", "CircleTangentToTwoLinesWithRadius", "CircleTangentToTwoDisjointCirclesWithRadius"}; 230 bool cmp(Circle x, Circle y) { return x.c < y.c || (x.c == y.c && x.r < y.r);} 231 232 Circle work1(Point p1, Point p2, Point p3) { 233 Vec nor1 = normal(p1 - p2); 234 Vec nor2 = normal(p2 - p3); 235 Point mid1 = (p1 + p2) / 2.0; 236 Point mid2 = (p2 + p3) / 2.0; 237 Point O = lineIntersect(mid1, nor1, mid2, nor2); 238 double r = ptDis(O, p1); 239 return Circle(O, r); 240 } 241 242 Circle work2(Point p1, Point p2, Point p3) { 243 Vec v11 = p2 - p1; 244 Vec v12 = p3 - p1; 245 Vec v21 = p1 - p2; 246 Vec v22 = p3 - p2; 247 double ang1 = (angle(v11) + angle(v12)) / 2.0; 248 double ang2 = (angle(v21) + angle(v22)) / 2.0; 249 Vec vec1 = Vec(cos(ang1), sin(ang1)); 250 Vec vec2 = Vec(cos(ang2), sin(ang2)); 251 Point O = lineIntersect(p1, vec1, p2, vec2); 252 double r = pt2Line(O, p1, p2); 253 return Circle(O, fabs(r)); 254 } 255 256 vector<double> work3(Circle C, Point p) { 257 vector<double> ret; 258 vector<Vec> tmp; 259 ret.clear(); 260 int cnt = tangent(p, C, tmp); 261 for (int i = 0; i < cnt; i++) { 262 double ang = angle(tmp[i]); 263 if (ang < 0) ang += pi; 264 ang = fmod(ang, pi); 265 ret.push_back(ang * 180 / pi); 266 } 267 return ret; 268 } 269 270 vector<Point> work4(Point p, Line l, double r) { 271 Vec vec = l.t - l.s; 272 Vec nor = normal(vec); 273 nor = nor / vecLen(nor) * r; 274 vector<Point> ret; 275 ret.clear(); 276 lineCircleIntersect(Line(l.s + nor, l.s + nor + vec), Circle(p, r), ret); 277 lineCircleIntersect(Line(l.s - nor, l.s - nor + vec), Circle(p, r), ret); 278 return ret; 279 } 280 281 vector<Point> work5(Line l1, Line l2, double r) { 282 Vec v1 = l1.t - l1.s; 283 Vec v2 = l2.t - l2.s; 284 Vec nor1 = normal(v1); 285 Vec nor2 = normal(v2); 286 nor1 = nor1 / vecLen(nor1) * r; 287 nor2 = nor2 / vecLen(nor2) * r; 288 vector<Point> ret; 289 ret.clear(); 290 ret.push_back(lineIntersect(l1.s + nor1, v1, l2.s + nor2, v2)); 291 ret.push_back(lineIntersect(l1.s + nor1, v1, l2.s - nor2, v2)); 292 ret.push_back(lineIntersect(l1.s - nor1, v1, l2.s + nor2, v2)); 293 ret.push_back(lineIntersect(l1.s - nor1, v1, l2.s - nor2, v2)); 294 return ret; 295 } 296 297 vector<Point> work6(Circle c1, Circle c2, double r) { 298 c1.r += r; 299 c2.r += r; 300 vector<Point> ret; 301 ret.clear(); 302 circleCircleIntersect(c1, c2, ret); 303 return ret; 304 } 305 306 char buf[100]; 307 308 int main() { 309 // freopen("in", "r", stdin); 310 // freopen("out", "w", stdout); 311 double x[10]; 312 while (cin >> buf) { 313 if (!strcmp(str[0], buf)) { 314 for (int i = 0; i < 6; i++) { 315 cin >> x[i]; 316 } 317 Circle tmp = work1(Point(x[0], x[1]), Point(x[2], x[3]), Point(x[4], x[5])); 318 printf("(%.6f,%.6f,%.6f)\n", tmp.c.x, tmp.c.y, tmp.r); 319 } else if (!strcmp(str[1], buf)) { 320 for (int i = 0; i < 6; i++) { 321 cin >> x[i]; 322 } 323 Circle tmp = work2(Point(x[0], x[1]), Point(x[2], x[3]), Point(x[4], x[5])); 324 printf("(%.6f,%.6f,%.6f)\n", tmp.c.x, tmp.c.y, tmp.r); 325 } else if (!strcmp(str[2] ,buf)) { 326 for (int i = 0; i < 5; i++) { 327 cin >> x[i]; 328 } 329 vector<double> ans = work3(Circle(Point(x[0], x[1]), x[2]), Point(x[3], x[4])); 330 sort(ans.begin(), ans.end()); 331 putchar('['); 332 for (int i = 0; i < ans.size(); i++) { 333 if (i) putchar(','); 334 printf("%.6f", ans[i]); 335 } 336 puts("]"); 337 } else if (!strcmp(str[3], buf)) { 338 for (int i = 0; i < 7; i++) { 339 cin >> x[i]; 340 } 341 vector<Point> ans = work4(Point(x[0], x[1]), Line(Point(x[2], x[3]), Point(x[4], x[5])), x[6]); 342 sort(ans.begin(), ans.end()); 343 putchar('['); 344 for (int i = 0; i < ans.size(); i++) { 345 if (i) putchar(','); 346 printf("(%.6f,%.6f)", ans[i].x, ans[i].y); 347 } 348 puts("]"); 349 } else if (!strcmp(str[4], buf)) { 350 for (int i = 0; i < 9; i++) { 351 cin >> x[i]; 352 } 353 vector<Point> ans = work5(Line(Point(x[0], x[1]), Point(x[2], x[3])), Line(Point(x[4], x[5]), Point(x[6], x[7])), x[8]); 354 sort(ans.begin(), ans.end()); 355 putchar('['); 356 for (int i = 0; i < ans.size(); i++) { 357 if (i) putchar(','); 358 printf("(%.6f,%.6f)", ans[i].x, ans[i].y); 359 } 360 puts("]"); 361 } else if (!strcmp(str[5], buf)) { 362 for (int i = 0; i < 7; i++) { 363 cin >> x[i]; 364 } 365 vector<Point> ans = work6(Circle(Point(x[0], x[1]), x[2]), Circle(Point(x[3], x[4]), x[5]), x[6]); 366 sort(ans.begin(), ans.end()); 367 putchar('['); 368 for (int i = 0; i < ans.size(); i++) { 369 if (i) putchar(','); 370 printf("(%.6f,%.6f)", ans[i].x, ans[i].y); 371 } 372 puts("]"); 373 } 374 } 375 return 0; 376 }
——written by Lyon