2015 ACM/ICPC 長春現場賽 E題

三分。

如果節點個數是奇數，那么直接列方程可以求解，因為，如果第一個圓半徑變大，必然導致最后一個圓的半徑變大，

所以，節點是奇數的時候，要么無解，要么只有一組解。

如果節點個數是偶數，如果奇數編號起點的線段長度之和不等于偶數編號起點的線段長度之和，那么必定無解，這個列方程也可以發現的。

剩下的就要三分求最優解了，邊界的確定有點小坑，第一個半徑是X，第二個半徑就是 L12-X，第三個半徑就是L23-L12+X.....寫出n個關于X的表達式，可以確定三分范圍。

至此，此題已解。

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std;const double PI=acos(-1.0); const double eps=1e-6;struct Point {double x,y;double r; }P[10000+10]; struct Line {double len; }L[10000+10]; int T,n; double r[10000+10];bool Equal(double a,double b) {if(fabs(a-b)<eps) return 1;return 0; }double Dis(int a,int b) {return sqrt((P[a].x-P[b].x)*(P[a].x-P[b].x)+(P[a].y-P[b].y)*(P[a].y-P[b].y)); }void read() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lf%lf",&P[i].x,&P[i].y);for(int i=1;i<=n;i++){if(i<n) L[i].len=Dis(i,i+1);else L[i].len=Dis(n,1);} }void print1() {double sum=0;for(int i=1;i<=n;i++)if(P[i].r<0){printf("IMPOSSIBLE\n");return ;}for(int i=1;i<=n;i++)sum=sum+P[i].r*P[i].r;printf("%.2lf\n",sum*PI);for(int i=1;i<=n;i++)printf("%.2lf\n",P[i].r); }double ff(double R) {r[1]=R;for(int i=2;i<=n;i++)r[i]=L[i-1].len-r[i-1];double sum=0;for(int i=1;i<=n;i++) sum=sum+r[i]*r[i];return sum; }void solve() {if(n%2==1){double len1=0,len2=0;for(int i=1;i<=n;i++){if(i%2==0) len2=len2+L[i].len;else len1=len1+L[i].len;}P[1].r=(len1-len2)/2.0;for(int i=2;i<=n;i++)P[i].r=L[i-1].len-P[i-1].r;if(!Equal(L[n].len-P[1].r,P[n].r)){printf("IMPOSSIBLE\n");return;}print1();}else if(n%2==0){double len1=0,len2=0;for(int i=1;i<=n;i++){if(i%2==1) len1=len1+L[i].len;else len2=len2+L[i].len;}if(len1!=len2) printf("IMPOSSIBLE\n");else{double left,right,mid,midmid;left=0; right=min(L[1].len,L[n].len);double sum=0;for(int i=1;i<=n;i++){if(i%2==1){sum=sum+L[i].len;if(sum<right) right=sum;}else{sum=sum-L[i].len;if(sum>left) left=sum;}}int tot=100;while(tot--){mid=(left+right)/2.0;midmid=(mid+right)/2.0;double k1=ff(mid);double k2=ff(midmid);if(k1-k2>eps) left=mid;else right=midmid;}for(int i=1;i<=n;i++)if(r[i]<0){printf("IMPOSSIBLE\n");return ;}printf("%.2lf\n",ff(midmid)*PI);for(int i=1;i<=n;i++) printf("%.2lf\n",r[i]);}} }int main() {scanf("%d",&T);while(T--){read();solve();}return 0; }

?

轉載于:https://www.cnblogs.com/zufezzt/p/4934062.html

總結

以上是生活随笔為你收集整理的HDU 5531 Rebuild的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。