题解 CF1354C2 【Not So Simple Polygon Embedding】

## 题目大意 求边长为$1$的正$(2\times n)$边形的最小外接正方形的边长。 $T$组数据。$T\le 200,n\le 200$，且$\bf{n}$**为奇数**。 ## 题解 与$\rm CF1354C2$不同，这次$n$换成了奇数。同样的，我们拿正六边形举例。  我们发现，这一次，问题变得棘手了起来。因为，这个正方形并不能很好地框住整个六边形。 我们不妨换一种思路。假设正方形的中心为坐标系原点$O(0,0)$，四条边与坐标轴平行，那么此时正方形的边长应该为$\max\{x_{max}-x_{min},y_{max}-y_{min}\}$才能将整个多边形包进去。 考虑到多边形最多旋转$\frac{\pi}{2\times n}$度，那么由于对称性，实际可能有关的点只有两个，即目前最靠右的点和$y$值最大且靠右边的那个点。（这里我们不妨假设这个多边形有两个顶点恰好在$x$轴上）。然后我们发现，随着旋转地不断变化，$C$的横坐标会不断减小，而$D$的横坐标会不断增大。根据对称性，只要旋转$\frac{\pi}{4\times n}$度就可以了。 ## 参考代码 ``` #include<bits/stdc++.h> #define up(l,r,i) for(int i=l;i<=r;i++) #define dn(l,r,i) for(int i=l;i>=r;i--) using namespace std; typedef long long LL; const int INF =2147483647; int qread(){ int w=1,c,ret; while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0'; while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0'; return ret*w; } const int MOD =998244353; const double pi=acos(-1); double f(double a,double b,double c,double d,double w){ //旋转 double x=a*cos(w)+b*sin(w),y=c*sin(w)+d*cos(w); return x>y?x:y; } int n; double t; int main(){ dn(qread(),1,T){ n=qread()*2,t=pi/n; double p0=(double)0.5/sin(t),p1=0; double q0=(double)0.5,q1=(double)0.5/tan(t); printf("%.12lf\n",f(p0,p1,q0,q1,t/2)*2.0); } return 0; } ```