BZOJ 1336&1337最小圆覆盖
2017-01-07 09:25:00       个评论    来源：SiriusRen的博客
我要投稿

（照着算法步骤写……）

```//By SiriusRen
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;double R,tempx,tempy,tempz,tmpx,tmpy,tmpz;
struct Point{double x,y;}point[100050],Ans;
double Sqr(double x){return x*x;}
double dis(Point a,Point b){return sqrt(Sqr(a.x-b.x)+Sqr(a.y-b.y));}
bool in_circle(Point x){return dis(Ans,x)<=R;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lf%lf",&point[i].x,&point[i].y);
random_shuffle(point+1,point+n);
for(int i=1;i<=n;i++)if(!in_circle(point[i])){
Ans.x=point[i].x,Ans.y=point[i].y,R=0;
for(int j=1;j<i;j++)if(!in_circle(point[j])){ ans.x="(point[i].x+point[j].x)/2;" ans.y="(point[i].y+point[j].y)/2;" r="dis(Ans,point[j]);" int="" k="1;k<j;k++)if(!in_circle(point[k])){" tempz="point[j].x-point[i].x;" tempx="2*(point[i].y-point[j].y)/tempz;" tempy="(Sqr(point[j].x)+Sqr(point[j].y)-Sqr(point[i].x)-Sqr(point[i].y))/tempz;" tmpz="point[k].x-point[j].x;" tmpx="2*(point[j].y-point[k].y)/tmpz;" tmpy="(Sqr(point[k].x)+Sqr(point[k].y)-Sqr(point[j].x)-Sqr(point[j].y))/tmpz;" f="" pre="">```