锐客网

  1. 首页 > it技术 > >

Codeforces|Codeforces Round #514 (Div. 2)-D. Nature Reserve

codeforces二分

Codeforces|Codeforces Round #514 (Div. 2)-D. Nature Reserve
文章图片

地址：http://codeforces.com/contest/1059/problem/D
思路：题目大意为找与x轴相切并且包含所有点的圆的最小半径。
一，对半径r二分，由于圆与x轴相切，圆心(x,y)中y=r,那么只要看x是否存在即可，对于每一个点找其为圆心，半径为r时在y=r直线上的范围，最后看所有的点是否有公共范围即可
二，对圆心(x,y)中x进行三分，x一定在所有点的x范围[l,r]内，并且其半径r的变换曲线是个U型的
Code 1:

#include #include #include using namespace std; typedef long double LD; struct node{ LD x; LD y; }; const int MAX_N=100005; const LD emp=1e-7; int n; node a[MAX_N]; int main() { LD ans=0; scanf("%d",&n); for(int i=0; i>a[i].x>>a[i].y; if(a[i].y>0) ++ans; else a[i].y=-a[i].y; } if(ans&&ans!=n) ans=-1; LD L=0,R=1e18+5,H; LD h,l,r,li,ri,t; while(R-L>emp&&ans!=-1){ h=(L+R)/2; l=-1e7; r=1e7; bool boo=true; for(int i=0; i

Code 2:
#include #include #include using namespace std; typedef long double LD; struct node{ LD x; LD y; }; const int MAX_N=100005; const LD eps=1e-7; int n; node a[MAX_N]; LD judge(LD x){ LD r=0,tmp; for(int i=0; i0) ++ans; else a[i].y=-a[i].y; } if(ans&&ans!=n) ans=-1; LD l=-1e8,r=1e8,t1,t2; int ss=100; while(ss--&&ans!=-1){ t1=l+(r-l)/3; t2=r-(r-l)/3; if(judge(t1)<=judge(t2)) r=t2; else l=t1; } if(ans!=-1){ ans=judge(l); printf("%Lf\n",ans); }else printf("-1\n"); return 0; }

【Codeforces|Codeforces Round #514 (Div. 2)-D. Nature Reserve】

    推荐阅读


    上一篇：自定义ViewPager+WebView跳转

    下一篇：Flutter 运行项目边框出现绿色的框框包围