hdu 5531 | 2015 ICPC 长春 regional onsite Rebuild (三分)

2017-10-14 · 3 min read · 三分

题目链接

题意：

有n个点，表示n个圆的圆心，问一组圆的半径，满足相邻(i,i+1)或者(n,1) 圆相外切。

思路：

我们发现确定第一个半径之后，其他的圆的半径似乎能解出来？

然后发现，其实只有n为奇数的时候能解出来，n为偶数不行。

那么我们可以奇数偶数分别处理。

对于奇数，直接解出来。式子不写了，很好推。

对于偶数，我们发现，最后会是一个关于r1的二次表达式。

一眼三分。然后训练的时候我就直接三分了。。？？？

三分的过程中判断一下是否所有圆的半径都满足实际意义。。。

然而这是错得，而且错得很显然。因为。。如果不满足实际意义，是根本没办法判断，该往哪个方向继续三分的。

正确的做法是，三分之前一定先确定定义域范围，在定义域内三分。

所以我们先解一个不等式组，把三分的范围解出来之后再进行三分orz

我对三分一无所知...

/* ***********************************************
Author :111qqz
Created Time :2017年10月14日 星期六 16时08分51秒
File Name :E.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair

 1using namespace std;
 2const double eps = 1E-10;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=1E4+7;
 7const double PI = acos(-1.0);
 8struct point
 9{
10    double x,y;
11    void input()
12    {
13    scanf("%lf %lf",&x,&y);
14    }

 1    double dis (point b)
 2    {
 3    double ret;
 4    ret = (x-b.x)*(x-b.x) + (y-b.y) * (y-b.y);
 5    return sqrt(ret);
 6    }
 7}p[N];
 8int n;
 9double a[N];
10int dblcmp( double d) { return d<-eps?-1:d>eps; }
11bool checkR( double R,int id)
12{
13    if (dblcmp(R)<0||dblcmp(R-a[id])>0) return false;
14    //if (dblcmp(R)<0) return false;
15    return true;
16}
17double area(double R)
18{
19    return  R*R ;
20}
21vector <double>vecR;
22double const DINF = 1E100;
23double calc(double R,bool debug)
24{
25    double ret = 0 ;
26    double lstR,curR;
27    lstR = R;
28    if (debug)
29    {
30    vecR.clear();
31    vecR.PB(R);
32    }
33    ret = area(R);
34    for ( int i = 1 ; i <= n-1 ; i++)
35    {
36    curR = a[i]-lstR;
37    if (debug) vecR.PB(curR);
38    ret += area(curR);
39    lstR = curR;
40    }
41   // cout<<"R:"<<R<<" ret:"<<ret<<endl;
42    return ret;
43}

 1double sanfen(double l, double r){
 2   double mid,midmid,ans;
 3    while (r-l>eps) {
 4    //cout<<"l:"<<l <<" r:"<<r<<endl;
 5        mid=(2*l+r)/3;
 6    midmid = (l+2*r)/3;
 7    //printf("A:%f B:%f\n",calc(mid,false),calc(midmid,false));
 8        if( dblcmp(calc(mid,false)-calc(midmid,false))>=0)    // >=就过了，<就wa???
 9            l=mid;
10        else
11            r=midmid;
12    }
13    ans=calc(l,true);
14    return ans;
15}
16void odd()
17{

 1    double lstR=0;
 2    double ans = 0 ;
 3    for ( int i = n ;  i >= 1 ; i--)
 4    {
 5    if (i%2) lstR += a[i];
 6    else lstR -= a[i];
 7    }
 8    lstR/=2;
 9    vecR.PB(lstR);
10    //cout<<"lstR:"<<lstR<<endl;
11    ans += area(lstR);
12    if (!checkR(lstR,1)) 
13    {
14    puts("IMPOSSIBLE");
15    return ;
16    }
17    for ( int i = 1 ; i <= n-1 ; i++)
18    {
19    double curR = a[i]-lstR;
20    if (!checkR(curR,i+1))
21    {
22        puts("IMPOSSIBLE");
23        return;
24    }
25    vecR.PB(curR);
26    ans +=area(curR);
27    lstR = curR;
28    }
29    ans*=PI;
30    printf("%.2f\n",ans);
31    for ( int i = 0 ; i < int(vecR.size()) ; i++)
32    {
33    printf("%.2f\n",vecR[i]);
34    }
35}
36double L,R;

 1int main()
 2{
 3#ifndef  ONLINE_JUDGE 
 4    freopen("./in.txt","r",stdin);
 5#endif
 6    int T;
 7    cin>>T;
 8    while (T--)
 9    {
10    scanf("%d",&n);
11    vecR.clear();
12    for ( int i = 1 ; i <= n ; i++) p[i].input();
13    for ( int i = 1 ; i <= n ; i++)
14    {
15        if (i==n)
16        a[i] = p[1].dis(p[n]);
17        else 
18            a[i] = p[i+1].dis(p[i]);
19        }
20//      for ( int i = 1 ; i <= n ; i++) printf("%f%c",a[i],i==n?'\n':' ');
21        //a[n+1] = a[1];
22        if (n%2==1)
23        {
24        odd();
25        continue;

 1        double tmp=0;
 2        for ( int i = n ; i >= 1 ; i--)
 3        {
 4        if (i%2) tmp+=a[i];
 5        else tmp-=a[i];
 6        }
 7        if (dblcmp(tmp)>0) { puts("IMPOSSIBLE");continue;}
 8        double L=0,R=a[1];//确定三分的范围
 9        tmp = 0 ;
10        for ( int i = 1 ; i <= n ; i++ )
11        {
12        int j = i+1;
13        if (j>n) j = 1;
14        tmp = a[i] - tmp;
15        if (i%2==1) R = min(R,tmp);
16        else L = max(L,-tmp);
17        }
18        if (L>R) { puts("IMPOSSIBLE");continue;}
19        double ans = sanfen(L,R);
20        ans*=PI;
21        printf("%.2f\n",ans);
22        for ( int i = 0 ; i < vecR.size() ; i++) printf("%.2f\n",vecR[i]);
23    }

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}