题解 AT5618 【[AGC039D] Incenters】

· · 题解

“在这里，你甚至可以学习平面几何”

比赛的时候这个题我似乎用三角函数的技巧硬推出来一个不知道对不对的式子，然后没实现完...... 然后发现标准做法完全不是这样）

定理1: 如图，A,B,C在\odot O上，在\triangle ABC中，作\angle BAC,\angle ACB,\angle CBA的平分线，分别交\odot O于F,D,E，并且三条角平分线交于一点I，则I是\triangle DEF的垂心。

证：

\textrm{设}\odot O\textrm{的周长为}c \because AF,BE,CD\textrm{分别是}\angle BAC,\angle CBA,\angle ACB\textrm{的平分线} \overset{\LARGE{\frown}}{CF}=\overset{\LARGE{\frown}}{FB}, \overset{\LARGE{\frown}}{BD}=\overset{\LARGE{\frown}}{DA} \therefore \overset{\LARGE{\frown}}{EC}+\overset{\LARGE{\frown}}{DF} = \frac{1}{2}c \therefore \angle EDC+\angle DEF=90^{\circ} \therefore DC\perp EF,\textrm{同理有}BE\perp DF,AF\perp ED \therefore I\textrm{是}\triangle DEF\textrm{垂心}

证毕。

有了这个结论之后，我们就可以把求内心转化成求另一个三角形的垂心了。而垂心的位置可以通过重心来转化计算：

定理2（欧拉线）:如图，A,B,C在\odot O上，D,E,F分别为AB,BC,CA中点，G,H分别为\triangle ABC的重心、垂心，连OH，则有G在OH上，且GH=2OG。

证：

\textrm{如下图，作直线}AO\textrm{交}\odot O\textrm{于}P,\textrm{连}BP,PC,PE,EH,OE

\because AP\textrm{是直径}\ \therefore AB\perp BP \textrm{又}\because CH\perp AB \therefore CH\parallel BP,\textrm{同理有} CP\parallel BH \therefore \textrm{四边形}BHCP\textrm{是平行四边形} \therefore BP=CH \because CH\parallel BP\ \therefore \angle PBC=\angle HCB \textrm{又}\because BE=EC \therefore \triangle BPE\ \cong \triangle CHE \therefore \angle PEB=\angle HEC\ \therefore P,E,H\textrm{共线} \therefore OE\textrm{是}\triangle PAH\textrm{中位线}\ \therefore OE=\frac{1}{2}AH \textrm{设}AE\textrm{与}OH\textrm{交于}G' \because OE\parallel AH\ \therefore \frac{OG'}{G'H}=\frac{G'E}{AG'}=\frac{OE}{AH}=\frac{1}{2} \therefore G'\textrm{是重心}\ \therefore GH=2OG

证毕。那么由这个结论，我们有\overrightarrow{OH}=3\overrightarrow{OG}。

在这题中，圆心O恰在原点，而平面中三点(x_A,y_A),(x_B,y_B),(x_C,y_C)组成的三角形重心之坐标为(\frac{x_A+x_B+x_C}{3},\frac{y_A+y_B+y_C}{3})，所以对于任意\triangle ABC，三段弧中点的坐标之和，就是\triangle ABC内心的坐标。

然后随便做做就好啦！

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define pi 3.14159265358979323846

using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = 3005;
int n,L;
ld t[MAXN],pre[2][2][MAXN][MAXN];

int main()
{
    cin >> n >> L;
    for(int i = 1; i<=n; i++)
        cin >> t[i];
    ld ansx = 0, ansy = 0;
    for(int i = 1; i<=n; i++)
        for(int j = i+1; j<=n; j++)
        {
            int cnt = j-i-1;
            ld tmp = pi*(t[i]+t[j])/L;
            ansx += cos(tmp)*(n-2*cnt-2), ansy += sin(tmp)*(n-2*cnt-2);
        }
    ansx /= 1ll*n*(n-1)*(n-2)/6;
    ansy /= 1ll*n*(n-1)*(n-2)/6;
    printf("%.12lf %.12lf\n",(double)ansx,(double)ansy);
    return 0;
}