前言
咕了好久才写，当时又发烧了所以没有交。
虽然有两道签，但一道时计算几何一道放了 T4 都没打，T1 赛时猜到结论和先看 T4 的都赢麻了，T1 赛时 \(π\) 只会背倒第九位精度炸了暴力都不对。
剩下的题当天太难受了都没改，改的两道都是 special judge 哎？
T1 小 h 的几何
- 九点圆圆心的证明详见 DrRatio 的博，Ishar-zdl 有没有证九点共圆但证明圆心位置更简便的方法。
结论：九点圆圆心在三条垂线交点与外心连线的中点上，坐标为 \((\dfrac{x_a+x_b+x_c}{3},\dfrac{y_a+y_b+y_c}{3})\)，也有代数证明方法（建系暴力算）。
直接统计每个点的贡献即可，\(π\) 可通过 c++ 库里的 M_PI。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const double pi=3.1415926535898;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar_unlocked();
for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n; double tmp,ansx,ansy;
signed main()
{
freopen("geometry.in","r",stdin),freopen("geometry.out","w",stdout);
read(n); for(int i=1,x;i<=n;i++)
read(x),ansx+=cos(1.0*x/1e9*pi),ansy+=sin(1.0*x/1e9*pi);
tmp=1.5/n; printf("%.12lf %.12lf",ansx*tmp,ansy*tmp);
}
T4 小j 的组合
题目和题面没有任何关系。
即除了树的直径其余的点都跑两遍，直径跑一边，处理出直径端点然后直接 dfs 就做完了。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define pb push_back
using namespace std;
const int N=110;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar_unlocked();
for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,s,t,mx,lca,tot,cnt,f[N],g[N],dad[N],nxt[N],ope[N],pos1[N],pos2[N],ans[N<<1];
vector<int>e[N];
void dfs1(int x,int fa)
{
pos1[x]=pos2[x]=x,dad[x]=fa;
for(int y:e[x]) if(y!=fa)
{
dfs1(y,x);
if(f[x]<f[y]+1)
pos2[x]=pos1[x],pos1[x]=pos1[y],g[x]=f[x],f[x]=f[y]+1;
else if(g[x]<f[y]+1) pos2[x]=pos1[y],g[x]=f[y]+1;
if(f[x]+g[x]>mx) s=pos1[x],t=pos2[x],lca=x,mx=f[x]+g[x];
}
}
void dfs2(int x,int fa,bool flag)
{
ans[++tot]=x,dad[x]=fa;
for(int y:e[x]) if(y!=fa&&y!=nxt[x]) dfs2(y,x,1);
if(nxt[x]) dfs2(nxt[x],x,0);
if(flag) ope[++cnt-n]=dad[x],ans[++tot]=cnt;
}
signed main()
{
freopen("combo.in","r",stdin),freopen("combo.out","w",stdout);
read(n),cnt=n;
for(int i=1,x,y;i<n;i++) read(x,y),e[x].pb(y),e[y].pb(x);
dfs1(1,0);
for(int i=s;i!=lca;i=dad[i]) nxt[i]=dad[i];
for(int i=t;i!=lca;i=dad[i]) nxt[dad[i]]=i;
dfs2(s,0,0); write(cnt-n),puts("");
for(int i=1;i<=cnt-n;i++) write(ope[i]),putchar_unlocked(' ');
puts(""); for(int i=1;i<=tot;i++) write(ans[i]),putchar_unlocked(' ');
}