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

题目链接

题意:

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

思路:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

我对三分一无所知…

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2017年10月14日 星期六 16时08分51秒
  4File Name :E.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define PB push_back
 20#define fst first
 21#define sec second
 22#define lson l,m,rt<<1
 23#define rson m+1,r,rt<<1|1
 24#define ms(a,x) memset(a,x,sizeof(a))
 25typedef long long LL;
 26#define pi pair < int ,int >
 27#define MP make_pair
 28
 29using namespace std;
 30const double eps = 1E-10;
 31const int dx4[4]={1,0,0,-1};
 32const int dy4[4]={0,-1,1,0};
 33const int inf = 0x3f3f3f3f;
 34const int N=1E4+7;
 35const double PI = acos(-1.0);
 36struct point
 37{
 38    double x,y;
 39    void input()
 40    {
 41    scanf("%lf %lf",&x,&y);
 42    }
 43
 44    double dis (point b)
 45    {
 46    double ret;
 47    ret = (x-b.x)*(x-b.x) + (y-b.y) * (y-b.y);
 48    return sqrt(ret);
 49    }
 50}p[N];
 51int n;
 52double a[N];
 53int dblcmp( double d) { return d<-eps?-1:d>eps; }
 54bool checkR( double R,int id)
 55{
 56    if (dblcmp(R)<0||dblcmp(R-a[id])>0) return false;
 57    //if (dblcmp(R)<0) return false;
 58    return true;
 59}
 60double area(double R)
 61{
 62    return  R*R ;
 63}
 64vector <double>vecR;
 65double const DINF = 1E100;
 66double calc(double R,bool debug)
 67{
 68    double ret = 0 ;
 69    double lstR,curR;
 70    lstR = R;
 71    if (debug)
 72    {
 73    vecR.clear();
 74    vecR.PB(R);
 75    }
 76    ret = area(R);
 77    for ( int i = 1 ; i <= n-1 ; i++)
 78    {
 79    curR = a[i]-lstR;
 80    if (debug) vecR.PB(curR);
 81    ret += area(curR);
 82    lstR = curR;
 83    }
 84   // cout<<"R:"<<R<<" ret:"<<ret<<endl;
 85    return ret;
 86}
 87
 88double sanfen(double l, double r){
 89   double mid,midmid,ans;
 90    while (r-l>eps) {
 91    //cout<<"l:"<<l <<" r:"<<r<<endl;
 92        mid=(2*l+r)/3;
 93    midmid = (l+2*r)/3;
 94    //printf("A:%f B:%f\n",calc(mid,false),calc(midmid,false));
 95        if( dblcmp(calc(mid,false)-calc(midmid,false))>=0)    // >=就过了,<就wa???
 96            l=mid;
 97        else
 98            r=midmid;
 99    }
100    ans=calc(l,true);
101    return ans;
102}
103void odd()
104{
105
106    double lstR=0;
107    double ans = 0 ;
108    for ( int i = n ;  i >= 1 ; i--)
109    {
110    if (i%2) lstR += a[i];
111    else lstR -= a[i];
112    }
113    lstR/=2;
114    vecR.PB(lstR);
115    //cout<<"lstR:"<<lstR<<endl;
116    ans += area(lstR);
117    if (!checkR(lstR,1)) 
118    {
119    puts("IMPOSSIBLE");
120    return ;
121    }
122    for ( int i = 1 ; i <= n-1 ; i++)
123    {
124    double curR = a[i]-lstR;
125    if (!checkR(curR,i+1))
126    {
127        puts("IMPOSSIBLE");
128        return;
129    }
130    vecR.PB(curR);
131    ans +=area(curR);
132    lstR = curR;
133    }
134    ans*=PI;
135    printf("%.2f\n",ans);
136    for ( int i = 0 ; i < int(vecR.size()) ; i++)
137    {
138    printf("%.2f\n",vecR[i]);
139    }
140}
141double L,R;
142
143int main()
144{
145#ifndef  ONLINE_JUDGE 
146    freopen("./in.txt","r",stdin);
147#endif
148    int T;
149    cin>>T;
150    while (T--)
151    {
152    scanf("%d",&n);
153    vecR.clear();
154    for ( int i = 1 ; i <= n ; i++) p[i].input();
155    for ( int i = 1 ; i <= n ; i++)
156    {
157        if (i==n)
158        a[i] = p[1].dis(p[n]);
159        else 
160            a[i] = p[i+1].dis(p[i]);
161        }
162//      for ( int i = 1 ; i <= n ; i++) printf("%f%c",a[i],i==n?'\n':' ');
163        //a[n+1] = a[1];
164        if (n%2==1)
165        {
166        odd();
167        continue;
168
169        }
170
171        double tmp=0;
172        for ( int i = n ; i >= 1 ; i--)
173        {
174        if (i%2) tmp+=a[i];
175        else tmp-=a[i];
176        }
177        if (dblcmp(tmp)>0) { puts("IMPOSSIBLE");continue;}
178        double L=0,R=a[1];//确定三分的范围
179        tmp = 0 ;
180        for ( int i = 1 ; i <= n ; i++ )
181        {
182        int j = i+1;
183        if (j>n) j = 1;
184        tmp = a[i] - tmp;
185        if (i%2==1) R = min(R,tmp);
186        else L = max(L,-tmp);
187        }
188        if (L>R) { puts("IMPOSSIBLE");continue;}
189        double ans = sanfen(L,R);
190        ans*=PI;
191        printf("%.2f\n",ans);
192        for ( int i = 0 ; i < vecR.size() ; i++) printf("%.2f\n",vecR[i]);
193    }
194
195
196  #ifndef ONLINE_JUDGE  
197  fclose(stdin);
198  #endif
199    return 0;
200}