题意
给定一个n边形，问是否可以以每个顶点为圆心画圆使得相邻顶点的圆外切，如果可以，问这些圆面积总和最小是多少，在总和最小的情况下每个圆面积是多少
思路
首先容易发现当一个圆半径固定，其它的也就固定了，不妨设以第一个点为圆心的圆半径为x，通过列式子可以发现n是奇数的情况与偶数的情况不同，所以要分类讨论。对于n是奇数的情况，x只能是固定的值，把它带进去计算，如果在某一条边上出现了负长度或超出了长度，那么就是无解，否则就把唯一解算出来。对于n是偶数的情况，通过计算可以发现这个n边形的边长需要满足一个条件，如果不行就是无解，其次可以通过在每一条边上半径不能为负且不能超出该边可以算出x的范围，而这个面积总和通过计算可知是一个二次函数，那么就是一个二次函数求区间最小值的问题，因为函数并不复杂，所以用中学的方法可以判断出x取何值时函数值最小，那么把它带入计算即可
代码
#include <cstdio>
#include <cmath>
#include <algorithm>
#define eps 1e-6
using namespace std;
int x[
10001],y[
10001];
double dis[
10001];
int t,n;
double xx,ans,l,r,temp,mid,add;
double calc(
double x)
{
double s=
0;
for(
int i=
0;i<n;i++)
{
s+=x*x;
if(x<
0||x>dis[i]||x>dis[(i-
1+n)%n])
return -
1;
x=dis[i]-x;
}
return acos(-
1)*s;
}
int main()
{
scanf(
"%d",&t);
while(t--)
{
scanf(
"%d",&n);
for(
int i=
0;i<n;i++)
scanf(
"%d%d",&x[i],&y[i]);
for(
int i=
0;i<n;i++)
dis[i]=
sqrt((x[(i+
1)%n]-x[i])*(x[(i+
1)%n]-x[i])+(y[(i+
1)%n]-y[i])*(y[(i+
1)%n]-y[i]));
if(n%
2==
1)
{
xx=
0;
for(
int i=
0;i<n;i++)
if(i%
2==
0)
xx+=dis[i];
else xx-=dis[i];
xx/=
2;
ans=calc(xx);
if(ans>
0)
{
printf(
"%.2f\n",ans);
for(
int i=
0;i<n;i++)
{
printf(
"%.2f\n",xx);
xx=dis[i]-xx;
}
}
else printf(
"IMPOSSIBLE\n");
}
else
{
l=
0;
r=dis[
0];
temp=
0;
for(
int i=
0;i<n;i++)
{
if(i%
2==
0)
{
temp+=dis[i];
r=min(r,temp);
}
else
{
temp-=dis[i];
l=max(l,temp);
}
}
if(r<l)
{
printf(
"IMPOSSIBLE\n");
continue;
}
add=
0;
for(
int i=
0;i<n-
1;i++)
if(i%
2==
0)
add+=dis[i];
else add-=dis[i];
if(
fabs(add-dis[n-
1])>eps)
{
printf(
"IMPOSSIBLE\n");
continue;
}
mid=
0;
for(
int i=
0;i<n-
1;i++)
if(i%
2==
0)
mid+=(n-
1-i)*dis[i];
else mid-=(n-
1-i)*dis[i];
mid/=n;
if(l<=mid&&r>=mid)
{
printf(
"%.2f\n",calc(mid));
xx=mid;
for(
int i=
0;i<n;i++)
{
printf(
"%.2f\n",xx);
xx=dis[i]-xx;
}
}
else
{
if(
fabs(l-mid)<=
fabs(r-mid))
xx=l;
else xx=r;
printf(
"%.2f\n",calc(xx));
for(
int i=
0;i<n;i++)
{
printf(
"%.2f\n",xx);
xx=dis[i]-xx;
}
}
}
}
return 0;
}
