计算几何 – 三角形的内心、垂心,AGC39-D题分析

计算几何 – 三角形的内心、垂心,AGC39-D题分析

这次Grand赛只会做A题。此D题在比赛时会写朴素的分别计算内心坐标并累加求平均,数据量一大就TLE,要结合几何关系把内心的计算转为坐标的线性运算,既降低了时间复杂度,又减少了浮点计算量。

对于三角形ABC来说,三个顶点的坐标已知。三角形的内心就是三角形内切圆的圆心,它到三角形三边的距离相等。三角形的内心与顶点坐标的关系式为:

x=(|BC|*x[A]+|AC|*x[B]+|AB|*x[C])/(|BC|+|AC|+|AB|)

y=(|BC|*y[A]+|AC|*y[B]+|AB|*y[C])/(|BC|+|AC|+|AB|)

本问题若用此法,则需要将所有可能的组合列出,时间复杂度为O(N^3),只能过一部分测试点。

本题特殊在于,所用三点均是单位圆上的点,要从单位圆上入手,相当于外接三角形的圆心是(0,0),半径为1是辅助条件。对于单位圆上的三点A,B,C来说,记A’为BC不含点A的弧的中点,B’与C’同理。这样,三角形ABC的内心I与三角形A’B’C’的垂心就重合(证明可根据圆周角定理,注意到A,I,A’是在同一条直线上)。三角形的垂心H,重心G,外心O都依H,G,O的顺序在一条直线上(欧拉线
https://mathtrain.jp/euler_line ),并且有|HG|:|GO|=2:1恒成立。而已证ABC的内心与A’B’C’的垂心H重合,所以只需要求A’B’C’的垂心H,又A’B’C’的外边O就是单位圆的圆心(0,0),只需要计算A’B’C’重心坐标即可。三角形重心坐标就是三个顶点坐标的平均值,这样可知G的坐标,就不难计算垂心H。

A’坐标与B,C的选法以及A,B,C的相对位置有关的,而和A的具体位置无关(A与A’分别在直线BC的两侧)。因此,对于A’的每个选择,可以通过找到对A’坐标的对最终答案的贡献,最后全加起来就可以计算出结果。 时间复杂度为O(N^2)。

发表评论

电子邮件地址不会被公开。 必填项已用*标注