hud3007 Buried memory

题目链接

最小圆覆盖

并不知道为什么是O(n)的,而且要随机化点的顺序

 #include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define rre(i,r,l) for(int i=(r);i>=(l);i--)
#define re(i,l,r) for(int i=(l);i<=(r);i++)
#define Clear(a,b) memset(a,b,sizeof(a))
#define inout(x) printf("%d",(x))
#define douin(x) scanf("%lf",&x)
#define strin(x) scanf("%s",(x))
#define LLin(x) scanf("%lld",&x)
#define op operator
#define CSC main
typedef unsigned long long ULL;
typedef const int cint;
typedef long long LL;
using namespace std;
const double eps=1e-;
double f(const long double &a){return a*a;}
void inin(int &ret)
{
ret=;int f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=;ch=getchar();}
while(ch>=''&&ch<='')ret*=,ret+=ch-'',ch=getchar();
ret=f?-ret:ret;
}
struct xl
{
double x,y;
xl(double x=.,double y=.):x(x),y(y){}
xl op + (const xl &rhs){return xl(x+rhs.x,y+rhs.y);}
xl op / (const double &rhs){return xl(x/rhs,y/rhs);}
void in(){douin(x),douin(y);}
};
double dis(const xl &a,const xl &b)
{
return sqrt(f(a.x-b.x)+f(a.y-b.y));
}
xl di[];
int n;
xl outoftriangle(const xl &A,const xl &B,const xl &C)
{
double bx=B.x-A.x,by=B.y-A.y;
double cx=C.x-A.x,cy=C.y-A.y;
double area=*(bx*cy-by*cx);
double x=(cy*(f(bx)+f(by))-by*(f(cx)+f(cy)))/area+A.x;
double y=(bx*(f(cx)+f(cy))-cx*(f(bx)+f(by)))/area+A.y;
return xl(x,y);
}
xl solve(double &r)
{
xl ret;
random_shuffle(di+,di+n+);
ret=di[];r=.;
re(i,,n)if(dis(di[i],ret)>r+eps)
{
ret=di[i],r=.;
re(j,,i-)if(dis(di[j],ret)>r+eps)
{
ret=(di[i]+di[j])/.;
r=dis(di[j],ret);
re(k,,j-)if(dis(di[k],ret)>r+eps)
{
ret=outoftriangle(di[i],di[j],di[k]);
r=dis(di[i],ret);
}
}
}
return ret;
}
int main()
{
while(scanf("%d",&n)&&n)
{
re(i,,n)di[i].in();
double r;
xl c=solve(r);
printf("%.2f %.2f %.2f\n",c.x,c.y,r);
}
return ;
}
上一篇:2018年第一篇行动笔记:Reading Log


下一篇:caffe arm