构造最小最大距离正三角形题解

题目大意

给定平面上三角形 \({ ABC }\) 的三个顶点坐标，构造一个正三角形 \({ A'B'C' }\)，使得原三角形顶点到新正三角形对应顶点的最大距离 \({ \max(|AA'|, |BB'|, |CC'|) }\) 最小。输出最优正三角形 \({ A'B'C' }\) 的坐标。

核心思路

这是一道经典的 极小极大几何优化问题 ，最优解满足两个关键性质：
1. 等距性 ：最优解必然使三个距离相等，即 \({ |AA'| = |BB'| = |CC'| = d }\)（否则可通过微调进一步缩小最大距离）。
2. 正三角形旋转约束 ：正三角形的顶点可通过向量旋转得到，即 \({ \overrightarrow{A'C'} = \overrightarrow{A'B'} \cdot \omega }\)（\({ \omega }\) 为60度或-60度旋转因子）。

利用 复数平面 简化旋转计算，结合三角不等式等号条件，可直接推导出 闭式数学解 ，完全避免数值优化的超时、精度不足等问题。

数学推导

1. 复数表示与旋转因子

将平面点用复数表示：设 \({ A, B, C }\) 对应的复数为 \({ a, b, c }\)，正三角形顶点 \({ A', B', C' }\) 对应的复数为 \({ a', b', c' }\)。

定义旋转因子：
- 逆时针60度旋转：\({ \omega_{\text{ccw}} = \frac{1}{2} + i\frac{\sqrt{3}}{2} }\)
- 顺时针60度旋转：\({ \omega_{\text{cw}} = \frac{1}{2} - i\frac{\sqrt{3}}{2} }\)

正三角形满足旋转关系（以逆时针为例）：
\({ c' = a' + (b' - a') \cdot \omega_{\text{ccw}} }\)

2. 等距性与最优解推导

设位移向量满足 \({ a' = a + k \cdot r_a }\)，\({ b' = b + k \cdot r_b }\)，\({ c' = c + k \cdot r_c }\)，其中 \({ |r_a| = |r_b| = |r_c| = 1 }\)，且 \({ r_a, r_b, r_c }\) 夹角为120度（保证等距性）。

结合正三角形旋转约束，通过三角不等式等号条件可推导出：
\({ K = a(1 - \omega) + b\omega - c }\)
最小距离 \({ d = \frac{|K|}{3} }\)，最优顶点为：
\({a' = a - \frac{K/3}{1 - \omega}}\)
\({b' = b - \frac{K/3}{\omega}}\)
\({c' = c + \frac{K}{3}}\)

分别计算 逆时针 和 顺时针 两种旋转方向的解，选择最大距离更小的那个作为最终结果。

代码实现

import math
import sys

def main():
    # 读取所有输入，兼容任意换行格式
    data = list(map(float, sys.stdin.read().split()))
    x1, y1, x2, y2, x3, y3 = data[:6]
    
    # 转换为复数，简化旋转计算
    A = complex(x1, y1)
    B = complex(x2, y2)
    C = complex(x3, y3)
    
    # 定义旋转因子：逆时针60度、顺时针60度
    omega_ccw = complex(0.5, math.sqrt(3) / 2)  # e^(iπ/3)
    omega_cw = complex(0.5, -math.sqrt(3) / 2)  # e^(-iπ/3)
    
    # 计算逆时针正三角形的解
    K_ccw = A * (1 - omega_ccw) + B * omega_ccw - C
    r_ccw = abs(K_ccw) / 3
    k3_ccw = K_ccw / 3
    a_ccw = A - k3_ccw / (1 - omega_ccw)
    b_ccw = B - k3_ccw / omega_ccw
    c_ccw = C + k3_ccw
    
    # 计算顺时针正三角形的解
    K_cw = A * (1 - omega_cw) + B * omega_cw - C
    r_cw = abs(K_cw) / 3
    k3_cw = K_cw / 3
    a_cw = A - k3_cw / (1 - omega_cw)
    b_cw = B - k3_cw / omega_cw
    c_cw = C + k3_cw
    
    # 选择最大距离最小的解
    if r_ccw < r_cw:
        p1, p2, p3 = a_ccw, b_ccw, c_ccw
    else:
        p1, p2, p3 = a_cw, b_cw, c_cw
    
    # 严格按6位小数输出
    print("{0:.6f} {1:.6f}".format(p1.real, p1.imag))
    print("{0:.6f} {1:.6f}".format(p2.real, p2.imag))
    print("{0:.6f} {1:.6f}".format(p3.real, p3.imag))

if __name__ == "__main__":
    main()

sb题,真他妈难

什么意思啊？

构造的三角形与原三角形无穷接近不就行了

谁能帮我解释一下？

直接approximation..

距离是单调的...

所以就往少的那个方向递归..

用复数做的……

用到了一个猜想……两个三角形重心重合。

Who can prove it？

orz cgy神new用数学+物理学方法！

本沙茶的沙茶方法：

PS:此题通过率被我提升了1个百分点（14%-->15%）

精度爆炸

最多递归两层

终于AC了。

用到了力学原理等方法得到了计算方法。

再用复数来写程序。

完全数学方法,不是逼近的。

不过我想知道怎么用逼近法来做。毕竟这不是数学试题。

ps:special case 是什么...开始那点狂WA

太好了,算法,讲一下.

唉.....几何高手看来还是没有兴趣来做这个啊....

怎么连gcd都用到了

讲一下算法