博客

题目大意

：给定一个凸N边形N个顶点坐标（N>=3），在N边形每个顶点上构造一个圆要求相邻两顶点的圆相切，求能构造出的最小总圆面积

数据范围

： 3 <= N <= 10000,  3 <= xi , yi <= 10000

题目解答

：三分法求下凸函数（复杂度O（N*log3(N)））

假设第一个点构造的圆半径为r，则其他点构造出的圆的半径可以依次表示出来，最后的答案是关于r的一个二次函数。

对于N边形分奇偶讨论：

• 
  N为奇数：此时关于r的二次函数没有r的一次项，则最终面积结果可以直接求解
  
• 
  N为偶数：此时关于r的二次函数有r的一次项，是一个下凸函数，想到三分求解
  

注意：三分的时候边界条件处理不好可能会导致WA，注意对最后二分出的结果取（l+r）/ 2作为答案

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define L(i) i<<1
#define R(i) i<<1|1
#define INF  0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-9
#define maxn 100100
#define MOD 1000000007

int n;
double dis[maxn],Ra[maxn];
double x[maxn],y[maxn];
double ans;

double get_dis(int i,int j)
{
    return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int solve(double r)
{
    double tmp = -r;
    for(int i = 0; i < n; i++)
    {
        tmp = dis[i] - tmp;
        Ra[i] = tmp;
        if(tmp < 0)
            return 0;
    }
    ans = 0;
    for(int i = 0; i < n; i++)
        ans += Ra[i] * Ra[i];
    ans *= pi;
    return 1;
}
int main()
{
    int t,C = 1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        dis[0] = 0;
        for(int i = 0; i < n; i++)
        {
            scanf("%lf%lf",&x[i],&y[i]);
            if(i)
                dis[i] = get_dis(i,i-1);
            if(i == n-1)
                dis[n] = get_dis(i,0);
        }
        double L = 0,R = dis[1];
        double sum = 0;
        for(int i = 1; i <= n; i++)
        {
            sum = dis[i] - sum;
            if(i & 1)
                R = min(R,sum);
            else
                L = max(L,-sum);
        }
        if(n & 1)
        {
            double r = sum / 2;
            if(!solve(r) || r < 0)
                printf("IMPOSSIBLE\n");
            else
            {
                printf("%.2f\n",ans);
                for(int i = 0; i < n; i++)
                    printf("%.2f\n",Ra[i]);
            }
        }
        else
        {
            if(L > R || fabs(sum) > eps)
            {
                printf("IMPOSSIBLE\n");
                continue;
            }
            double l = L,r = R;
            while(l + eps < r)
            {
                double mid = l + (r - l) / 3;
                double mmid = r - (r - l) / 3;
                solve(mid);
                double ans1 = ans;
                solve(mmid);
                double ans2 = ans;
                if(ans1 < ans2)
                    r = mmid;
                else
                    l = mid;
            }
            solve(l);
            printf("%.2f\n",ans);
            for(int i = 0; i < n; i++)
                printf("%.2f\n",Ra[i]);
        }
    }
    return 0;
}