题解 AT5618 【[AGC039D] Incenters】
Caro23333
2020-04-04 17:31:17
_**“在这里，你甚至可以学习平面几何”**_
比赛的时候这个题我似乎用三角函数的技巧硬推出来一个不知道对不对的式子，然后没实现完...... 然后发现标准做法完全不是这样）
#### 定理$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{的平分线}$$
$$\therefore \overset{\LARGE{\frown}}{AE}=\overset{\LARGE{\frown}}{EC},
\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$内心的坐标**。
然后随便做做就好啦！
代码：
```cpp
#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;
}
```