UVA 12304：球面幾何綜合模板（圓交點、切線、內外切圓等）

圓結構與核心算法

struct Circle { Point c; double r; Point point(double a) { return Point(c.x+cos(a)*r, c.y+sin(a)*r); } };

// 直線圓交點
int getLineCircleIntersection(Point p, Vector v, Circle c, vector& sol) { /* 解一元二次方程 */ }

// 兩圓交點
int getCircleCircleIntersection(Circle c1, Circle c2, vector& sol) { /* 余弦定理求夾角 */ }

// 點到圓切線
int getTangents(Point p, Circle c, Vector* v) { /* 向量旋轉 */ }

// 兩圓公切線（內/外）
int getCircleTangents(Circle A, Circle B, Point* a, Point* b) { /* 懸線法，分情況討論 */ }

// 三角形外切圓/內切圓
Circle CircumscribedCircle(Point p1, Point p2, Point p3);
Circle InscribedCircle(Point p1, Point p2, Point p3);

題目具體要求

輸入多種操作指令（CircumscribedCircle, InscribedCircle, TangentLineThroughPoint, CircleThroughAPointAndTangentToALineWithRadius, CircleTangentToTwoLinesWithRadius, CircleTangentToTwoDisjointCirclesWithRadius），調用對應函數並格式化輸出坐標/角度。

關鍵技巧

• 所有幾何判斷用 dcmp 處理精度。
• 角度輸出需轉為 [0,180) 度並排序。
• 圓心坐標輸出保留 6 位小數，按 x 後 y 排序。
• 模板代碼極長，建議封裝成庫文件複用。