一、题意
No response.T_T
二、思路
分$n$为奇数或者偶数讨论。
如果$n$是奇数,列出不等式组:$r_1+r_2=d_{1},r_2+r_3=d_{2},r_3+r_4=d_{3},\cdots,r_{n-1}+r_n=d_{n-1},r_n+r_1=d_n$,可以解出,$r_1=\frac{d_{1}+d_{3}+d_{5}+\cdots-d_{2}-d_{4}-\cdots}{2}$,然后再用上述式子依次算出$r_2$至$r_n$。最后判断$r_1$至$r_n$中是否存在负数即可。
如果$n$是偶数。如果奇数起点的边之和$s_1=d_1+d_3+d_5+\cdots+d_{n-1}$不等于$s_2=d_2+d_4+d_6+\cdots+d_n$,说明无解,否则,一定可以三分枚举出$r_1$,然后推出其他半径。要注意的是,三分的下界和上界需要处理出来。否则,面积关于$r_1$的二次函数在$[low,high]$区间内不一定只有一个极小值。最后判断是否所有半径都大于$0$。
三、代码
#include<bits/stdc++.h> using namespace std; ); struct point { double x, y; } p[]; ], ansr[]; int n; inline bool eq(double x, double y) { ); } inline double dis(point a, point b) { return hypot(a.x - b.x, a.y - b.y); } double calc(double r1) { ansr[] = r1; double sum = PI * r1 * r1, nr; ; i <= n; ++i) { ansr[i] = d[i - ] - ansr[i - ]; sum += PI * ansr[i] * ansr[i]; } return sum; } int main() { // freopen("e.in", "r", stdin); int T; for(scanf("%d", &T); T--;) { ; scanf("%d", &n); ; i <= n; ++i)scanf("%lf %lf", &p[i].x, &p[i].y); ; i <= n; ++i)d[i] = dis(p[i], i < n ? p[i + ] : p[]); ) { ; ; i <= n; i++) { )fz += d[i]; else fz -= d[i]; } ansr[] = fz / ; ; i <= n; ++i)ansr[i] = d[i - ] - ansr[i - ]; ] + ansr[n], d[n]))imp = ; } else { , t2 = ; ; i <= n; ++i) { )t1 += d[i]; else t2 += d[i]; } ; else { , high = min(d[], d[n]), lmid, rmid, s1, s2, sum = ; ; i <= n; ++i) { )sum += d[i], high = min(high, sum); else sum -= d[i], low = max(low, sum); } ; while(ttt--) { lmid = (low + high) / ; rmid = (lmid + high) / ; s1 = calc(lmid), s2 = calc(rmid); if(s1 < s2)high = rmid; else low = lmid; } double r1; if(calc(low) < calc(high))r1 = low; else r1 = high; calc(r1); } } ; i <= n; ++i) { )imp = ; } if(imp) puts("IMPOSSIBLE"); else { ; ; i <= n; ++i)ans += ansr[i] * ansr[i]; ans *= PI; printf("%.2f\n", ans); ; i <= n; ++i)printf("%.2f\n", ansr[i]); } } ; }