博客

分析：这个题就是让我们给一个多边行每一个顶点为圆心画圆，然后相邻顶点的园是像相切的，使面积最小。

题解：这个题，如果是奇数多边形的话，可以推导出来，每个圆的半径是固定的。以三角形为例即可证明。如果顶点是偶数个，那个就三分一条边，因为可以以四边形证明，半径越趋于边长的一半，他的总面积就会最小，符合凸性函数的性质，所以可以三分答案。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const double PI=acos(-1.0);
const double eps=1e-8;
struct node{
    double x,y;
}point[10005];
double l[10005],r[10005];
int n;
double f(node a,node b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double check(double x)
{
    r[0]=x;
    double ans=r[0]*r[0];
    for(int i=1;i<n;i++){
        r[i]=l[i-1]-r[i-1];
        ans+=r[i]*r[i];
    }
    return ans;
}
double sanfen(double left,double right)
{
    double midl,midr;
    while(right-left>eps)
    {
        midl=(left+right)/2;
        midr=(midl+right)/2;
        if(check(midl)<=check(midr)) 
			right=midr;
        else 
			left = midl;
    }
    return left;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=0;i<n;i++) 
			scanf("%lf%lf", &point[i].x, &point[i].y);
        for(int i=0;i<n;i++) 
			l[i]=f(point[i], point[(i+1)%n]);
		r[0]=0;
        for(int i=0;i<n;i++){
            if(i%2) r[0]-=l[i];
            else  r[0]+=l[i];
        }
        if(n%2){
            r[0]/=2;
            double ans=PI*r[0]*r[0];
            int flag1=0;
            if(r[0]>-eps&&r[0]<=l[0]){
                for(int i=1;i<n;i++){
                    r[i]=l[i-1]-r[i-1];
                    if(r[i]<-eps||r[i]>l[i]){
                        flag1=1;
                        break;
                    }
                    ans+=PI*r[i]*r[i];
                }
            }
            else flag1=1;
            if(flag1) 
				printf("IMPOSSIBLE\n");
            else{
                printf("%.2f\n",ans);
                for(int i=0;i<n;i++) 
					printf("%.2f\n",r[i]);
            }
        }
        else{
            double flag1=0,flag2=1e9;
            if(fabs(r[0])>eps){
				printf("IMPOSSIBLE\n");
				continue;
			}
            double sum=0;
            for(int i=1;i<n;i++){
                sum=l[i-1]-sum;
                if(i%2) 
					flag2=min(flag2,sum);
                else 
					flag1=max(flag1,-sum);
            }
            double ans=sanfen(flag1,flag2);
            if(flag1>flag2) 
				printf("IMPOSSIBLE\n");
            else{
                printf("%.2f\n",check(ans)*PI);
                for(int i=0;i<n;i++) 
					printf("%.2f\n",r[i]);
            }
        }
	}
	return 0;
}