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}