UVA 11731 旁切圆问题详解：从旁心坐标到外公切线的计算几何实践

在 UVa 的老题库里11731 这题不算难但挺唬人。题目名字叫 Ex-circles翻译过来就是旁切圆。不少第一次见到这题的人第一反应是完了又得去翻几何公式。尤其是国内很多教材讲旁切圆讲得少最多在三角形五心那里提一嘴旁心然后就直接跳到竞赛题中间缺了一大段实操经验。这篇博客就是来补这段经验的。我会把旁切圆相关的前置知识、个人选择的解题路线、完整可提交的代码以及本地调试和提交环境上的踩坑记录一次性讲清楚。这篇文章适合刚接触计算几何题的选手也适合那种被公式劝退、想找一种“无脑但正确”做法的人。1. 题目拆解先搞清楚它在求什么1.1 题面到底让你算什么UVA 11731 给的是一个三角形的三条边长要求的是三个旁切圆两两之间的外公切线长度之和。这里有个容易混淆的点题目要的是外公切线不是内公切线。两个圆不管是外离还是相交外公切线都画得出来但旁切圆两两之间是外离的所以既有外公切线也有内公切线。题目明确要的是外公切线画出来是对称的两条长度相等所以每一对圆只要算一次长度就行。很多人看到 Ex-circles 这个标题会以为要处理一堆复杂的圆和圆相交关系。实际上这道题本质上只考两件事第一你能不能算出三个旁切圆的半径第二你能不能算出三个旁心之间的距离。一旦半径和圆心距都有了外公切线长度就是一个非常朴素的勾股定理。换句话说这不是一道考“灵感”的题而是一道考“基础计算”的题思路比技巧重要得多。1.2 为什么这题值得单独写一篇我在 UVA 上刷题时遇到过不少几何题要么是公式极其复杂要么是精度卡到你怀疑人生。11731 属于那种表面上看着吓人、实际做起来却很老实的题目。它既没有复杂的凸包也没有要命的极角排序只要你愿意耐着性子把基本量算出来答案就自己冒出来了。但它的坑点在于网上很多题解直接甩一个化简后的公式却不解释公式是怎么来的。这样做的后果是换个输入顺序、换个问法你就懵了。所以我在这篇博文里会重点讲公式的来路同时给出一套“不依赖化简公式直接用坐标硬算”的方案。坐标法虽然看起来步骤多但它每一步都可验证、可调试对新手非常友好。2. 前置知识旁心、旁切圆和两个常用公式2.1 旁切圆是干什么的三角形有三个旁切圆每个旁切圆都同时与三角形的一条边和另外两条边的延长线相切。比如 A-旁切圆它和边 BC 相切同时和 AB、AC 的延长线相切。旁切圆的圆心叫作旁心记为 I_a、I_b、I_c。旁心有一个重要性质它是三角形一个内角平分线和另外两个外角平分线的交点。这个性质很关键。如果你用几何画板随便画一个三角形把三个旁心都画出来会发现它们都在三角形外部而且三个旁心之间构成的三角形其实和原三角形有非常整齐的对偶关系。不过这道题不需要用到那么深你只需要记住旁心是有明确的坐标公式的不是只能靠尺规作图找出来的点。2.2 旁切圆半径怎么算旁切圆半径是解题的第一个关键量公式非常简洁。设三角形三条边为 a、b、c半周长 s (abc)/2面积用海伦公式算Δ sqrt(s * (s-a) * (s-b) * (s-c))那么三个旁切圆半径分别是r_a Δ / (s-a)r_b Δ / (s-b)r_c Δ / (s-c)这个公式和普通内切圆半径 r Δ / s 形式上非常一致区别就是把分母的 s 换成了 s-a。为什么会这样因为旁切圆到三边所在直线的距离都相等都等于 r_a。你把三角形面积拆成三个小三角形的带符号面积之和。对 A-旁切圆来说它在 BC 边外侧所以三角形 I_aBC 的面积是负的而三角形 I_aCA 和 I_aAB 的面积是正的加到一起就是Δ 1/2 * r_a * (b c - a) r_a * (s-a)等号两边一除就得到了上述公式。这个推导虽然带符号但只要画一下图就能看懂。实际编程时直接套海伦公式算面积再除以对应的 s-a 就行了完全不用去管正负号问题。2.3 旁心的重心坐标从哪来有了半径下一步要算旁心坐标。最方便的办法是利用重心坐标公式。如果三角形三个顶点的笛卡尔坐标为 A、B、C那么旁心的重心坐标是I_a (-a * A b * B c * C) / (-a b c)I_b (a * A - b * B c * C) / (a - b c)I_c (a * A b * B - c * C) / (a b - c)注意这里的 a、b、c 分别指的是顶点 A、B、C 的对边长度也就是 BC、CA、AB 的长度。分母其实就是 bc-a、ac-b、ab-c因为三角形任意两边之和大于第三边所以分母都是正数不会除出负数。很多初学者看到这个带负号的公式会慌其实它就是普通的加权平均只是某个顶点前面的系数是负的表示这个点落在对应顶点的“对面”。这个公式的来源是角平分线定理如果你不想记推导直接当成结论用也完全可以。我在实际比赛里不会现场推这个直接背过因为这是一个非常通用的结论。3. 解题路线选公式还是选坐标3.1 公式化简路线为什么容易翻车有的题解说这道题可以继续化简最后得到一些非常漂亮的式子比如旁切圆两两之间的外公切线长度可以直接用边长表示甚至最后答案和三角形周长有某种比例关系。我确实见过这类题解算出来的结果在某些特殊三角形下看起来非常优雅。但问题是这种化简过程对一般人来说既不直观又容易出错。尤其当你把三个外公切线长度加起来之后式子会变得很长嵌套着各种根号。一旦其中某一步正负号弄反后面全盘皆输。更麻烦的是如果题目数据是用浮点数输入的化简后的公式经常会因为减法相消产生比较大的精度误差。所以我个人在比赛里遇到这种几何题第一选择永远是坐标法而不是强行化简。3.2 坐标法为什么稳坐标法的思路很朴素把一个几何问题变成代数问题。具体到这道题就是把三角形放到平面直角坐标系里算出三个旁心的坐标然后用欧氏距离公式算圆心距。整个过程只涉及加减乘除、开根号每一步都可以用计算器验证。对于编程题来说代码量也不大大约四五十行就能写完。坐标法的另一个好处是通用性极强。以后你遇到“求两个圆公切线长度”“求旁心三角形面积”这类变体题只要改几个参数就能复用。相比之下死记硬背化简公式每次遇到新题都要重新推导效率太低。所以我强烈建议几何题优先坐标法只有在坐标法太麻烦时才考虑公式法。3.3 外公切线长度的几何解释现在来说最后一个核心公式。已知两个圆的圆心距为 d半径分别为 r1 和 r2那么两圆外公切线的长度 L 是L sqrt(d * d - (r1 - r2) * (r1 - r2))这个公式的几何解释是这样的过小圆圆心作大圆半径的平行线你会发现两个切点之间的距离恰好等于一个直角三角形的斜边。这个直角三角形的一条直角边是圆心距 d另一条直角边是半径之差 |r1 - r2|斜边就是外公切线段的长度。所以直接勾股定理就出来了。要注意这个公式成立的前提是 d |r1 - r2|也就是两个圆不能是一个包含另一个的关系。对于本题的三个旁切圆它们两两之间都是外离的所以条件一定满足。但程序里为了保险还是要对根号底下的数做个非负处理防止浮点误差导致出现 -1e-12 这种负数。4. 完整实现C 代码与每一步说明4.1 坐标系的选取我习惯把三角形的一个顶点放在原点另一个顶点放在 x 轴上。假设三边输入顺序为 a、b、c分别对应角 A、B、C 的对边那么可以这样建系A (0, 0)B (c, 0)C (x, y)其中 x 和 y 用余弦定理求。因为 AC bBC aAB c所以x (b² c² - a²) / (2c)y sqrt(b² - x²)这里取 y 为正数表示 C 点在第一象限。这样三角形就完全定下来了三个顶点的坐标都是已知量。代码里需要注意x 的表达式本质上来自余弦定理分母是 2c千万别写成 2a 或者 2b这是新手很容易犯的低级错误。4.2 旁心坐标的代码实现有了 A、B、C 的坐标直接用重心坐标公式算三个旁心。代码里我习惯先定义一个 Point 结构体然后写一个简单的加权平均函数。注意运算符重载要定义好double 乘 Point 的运算在 C 里不会自动支持需要自己写。struct Point { double x, y; Point(double x 0, double y 0) : x(x), y(y) {} }; Point operator(Point A, Point B) { return Point(A.x B.x, A.y B.y); } Point operator-(Point A, Point B) { return Point(A.x - B.x, A.y - B.y); } Point operator*(double k, Point A) { return Point(k * A.x, k * A.y); } double dist(Point A, Point B) { double dx A.x - B.x, dy A.y - B.y; return sqrt(dx * dx dy * dy); }然后旁心坐标就是Point IA (-a * A b * B c * C) / (b c - a); Point IB (a * A - b * B c * C) / (a c - b); Point IC (a * A b * B - c * C) / (a b - c);这里除法是按分量除的需要给 Point 结构体再写一个除法运算符。你可以直接写一个成员函数完成这个操作避免重复代码。4.3 完整可运行代码下面是一份完整的 C 代码。我按 UVA 老题的风格用while (scanf(...))读入遇到三个 0 就结束。输出格式我用了%.3f如果你碰到的题面要求六位小数把%.3f改成%.6f就行。#include bits/stdc.h using namespace std; const double eps 1e-12; struct Point { double x, y; Point(double x 0, double y 0) : x(x), y(y) {} }; Point operator(Point A, Point B) { return Point(A.x B.x, A.y B.y); } Point operator-(Point A, Point B) { return Point(A.x - B.x, A.y - B.y); } Point operator*(double k, Point A) { return Point(k * A.x, k * A.y); } Point operator/(Point A, double k) { return Point(A.x / k, A.y / k); } double dist(Point A, Point B) { double dx A.x - B.x, dy A.y - B.y; return sqrt(dx * dx dy * dy); } int main() { double a, b, c; int kase 0; while (scanf(%lf%lf%lf, a, b, c) 3) { if (a 0 b 0 c 0) break; double s (a b c) / 2.0; double area sqrt(s * (s - a) * (s - b) * (s - c)); double rA area / (s - a); double rB area / (s - b); double rC area / (s - c); double xC (b * b c * c - a * a) / (2.0 * c); double yC sqrt(b * b - xC * xC); Point A(0, 0), B(c, 0), C(xC, yC); Point IA (-a * A b * B c * C) / (b c - a); Point IB (a * A - b * B c * C) / (a c - b); Point IC (a * A b * B - c * C) / (a b - c); auto tangent [](Point P, double r1, Point Q, double r2) { double d dist(P, Q); double v d * d - (r1 - r2) * (r1 - r2); if (v 0) v 0; return sqrt(v); }; double ans tangent(IA, rA, IB, rB) tangent(IB, rB, IC, rC) tangent(IC, rC, IA, rA); printf(Case %d: %.3f\n, kase, ans); } return 0; }这个代码的核心逻辑非常短算面积、算半径、算坐标、算圆心距、累加。我在本地用很多组数据测过包括等边三角形和直角三角形结果都符合预期。4.4 用几个特例验证正确性写几何题最怕代码跑不出正确答案还不确定公式对不对。我每次写完都会先用特殊数据验证。比如边长是 3、4、5 的直角三角形半周长 s6面积 Δ6三个旁切圆半径分别是 2、3、6。用上面代码算出三个外公切线长度分别是 7、8、9总和是 24。这个结果很漂亮可以用来快速检查程序有没有明显的运算错误。再比如等边三角形边长为 L。三个旁切圆半径相等旁心之间的距离都是 2L所以外公切线长度就是 2L三条加起来是 6L。如果程序输出这个结果说明旁心坐标和半径计算基本没问题。等边三角形由于高度对称是检验符号错误的最佳工具。5. 调试与提交经验5.1 浮点误差与 NaN 陷阱计算几何题最常见的坑就是浮点误差。这道题里最危险的一行是sqrt(v)因为 v 理论上应该是一个非负数但由于 double 的精度限制v 有可能算出 -1e-15 这种极小负数。直接对负数开根号在部分环境下会得到 NaN最终输出变成-1.#IND或者nan然后你就开始疯狂查代码查了半天发现不是逻辑错是精度问题。我的做法是在开根号之前加一行if (v 0) v 0;或者v max(0.0, v);。这个操作不影响正确答案因为 v 小于 0 的时候绝对值也非常小取 0 和取 -1e-15 的根号结果几乎一样。这个习惯我建议所有做计算几何的人都要养成能帮你省去大量调试时间。还有一个容易被忽略的问题不要把半径算出来之后再去用面积反推。因为面积本身也是用 sqrt 算出来的会有微小误差但只要不参与复杂运算这个误差不会影响最终结果。真正危险的是两个很大很接近的数相减比如圆心距平方和半径差平方很接近时v 值会丢失精度。这种情况下尽量保持中间量都是 double不要转 float。5.2 老平台提交的格式问题UVA 是一个很老的在线评测平台它的编译器版本和对语法的支持程度跟现代比赛环境不完全一样。有些新写的代码在本地跑得好好的一提交就编译错误原因可能是用了 C17 的某些新特性。我这份代码只用到了基础语法和 lambda 表达式C11 就能过UVA 上选 C11 或 C14 提交一般没问题。输出格式也要特别注意。UVA 的题目对行末空格、输出顺序都很敏感最好按题面要求严格输出。如果题面要求保留三位小数就老老实实三位多一个或少一个都可能导致 Presentation Error。另外老题目很多是while (scanf(...) 3)循环读入不用读到 EOF 的题反而少所以代码里用 3是安全的。5.3 WSL2 下本地测试的一点心得最近有人在群里问为什么在 WSL2 里跑 UVa 相关工具会提示uva is not available。我猜可能是某个第三方命令行提交工具或者脚本没有装好或者环境变量配置不对。其实做 UVa 题完全不需要依赖这种工具本地只要有一个能编译 C 的编译器就够了。在 WSL2 里最稳妥的流程是写一个main.cpp用g main.cpp -o main编译然后把样例数据存成in.txt执行./main in.txt看输出。如果想测试多组数据就多建几个输入文件一条命令换着跑。UVA 的网页提交页面本身就能直接粘代码不需要额外装任何 CLI 工具。如果你在 WSL2 里敲g --version提示找不到说明还没装编译器执行sudo apt update sudo apt install g装一下就行。装完之后用上面这个流程几分钟就能把代码验证完再打开网页提交整个过程没有任何障碍。6. 这道题带给我的几点体会刷完 UVa 11731我最大的感受是很多几何题不是难在思路而是难在“敢不敢动手算”。我见过不少人看到旁切圆三个字就开始背诵各种内切圆外接圆公式结果背岔了还不如老老实实建坐标系硬算。坐标法虽然看起来笨但它的容错率高每一步都可以验证尤其适合新手建立信心。另外这道题对精度处理的要求也很有代表性。以后你做任何计算几何题都应该默认浮点误差存在提前做好保护而不是等 WA 了再去排查。我的习惯是凡是遇到sqrt一律先检查根号内部是否非负凡是遇到除法一律想想分母有没有可能为零凡是输出浮点数一律明确指定保留几位小数。如果你是把这道题当作练习我建议你做完 11731 之后尝试把题目改一改比如求三个旁切圆两两之间的内公切线长度或者求三个旁心构成的三角形面积。你会发现只要掌握了坐标法和旁心坐标公式这些变体题你都能顺手解出来。这才是刷题真正的价值所在。