算法 三分法
【codeforce514 D. Nature Reserve 凸函数三分】codeforce514 D. Nature Reserve
给定若干个点，求包含所有点且与x轴相切的圆的最小半径
#include
using namespace std;
const int MAX=1e5+5;
const double eps=1e-8;
int n;
paira[MAX];
double l,r,midl,midr,lr,rr;
double dis(double x1,double x2,double y2)
{
return (x1-x2)*(x1-x2)+y2*y2;
}
double getr(double x)
{
double R=0.0;
for(int i=0;
i0) yl=1;
else if(a[i].second<0) yr=1;
else ++yo;
}
if((yl&&yr)||yo>1) {printf("-1\n");
continue;
}
if(fabs(l-r)eps) l=midl;
else r=midr;
}
printf("%.8f\n",(lr+rr)/2.0);
}
return 0;
}
推荐阅读
- 分治|全排列算法整理
- 数论|hdu 5322 Hope（分治+NTT）
- codeforces|Codeforces Global Round 10 D. Omkar and Bed Wars(思维，分块)
- hdu|【hdu 5354】Bipartite Graph【分治 并查集】
- Pow(x, n) （计算x的n次方）
- 模板|LOJ #2340. 「WC2018」州区划分(FMT子集卷积)
- 点分治|点分治时间复杂度
- LeetCode 973 TopK问题 分治算法