题目大意:
给定n个点,求面积最小的园覆盖所有点.其中(n leq 10^6)
题解:
恩。。。
刚拿到这道题的时候...
什么？？？最小圆覆盖不是(O(n^3))的随机增量算法吗？？？？？
(10^6)又是个什么鬼？？？？？？？？？
然后去%了popoqqq大爷的题解...原来这道题数据是随机的啊。。。
随机数据有一个性质,在凸包上的点不超过(logn)
所以我们求凸包然后在上面跑随机增量算法即可
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 1000010;
const double eps = 1e-9;
inline int dcmp(const double &x){
if(x < eps && x > -eps) return 0;
return x > 0 ? 1 : -1;
}
struct Point{
double x,y;
Point(const double &a = 0,const double &b = 0){x=a;y=b;}
void print(){
printf("Point : (%lf,%lf)
",x,y);
}
};
typedef Point Vector;
inline Vector operator + (const Vector &a,const Vector &b){
return Vector(a.x+b.x,a.y+b.y);
}
inline Vector operator - (const Vector &a,const Vector &b){
return Vector(a.x-b.x,a.y-b.y);
}
inline Vector operator / (const Vector &a,const double &b){
return Vector(a.x/b,a.y/b);
}
inline bool operator < (const Point &a,const Point &b){
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
inline double operator * (const Vector &a,const Vector &b){
return a.x*b.x + a.y*b.y;
}
inline double cross(const Vector &a,const Vector &b){
return a.x*b.y - a.y*b.x;
}
inline double sqr(const double &x){
return x*x;
}
inline double dis(const Point &a,const Point &b){
return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}
inline Point getPoint(const Point &p0,const Point &p1,const Point &p2){
double a1 = p1.x - p0.x,b1 = p1.y - p0.y,c1 = (a1*a1 + b1*b1)/2.0;
double a2 = p2.x - p0.x,b2 = p2.y - p0.y,c2 = (a2*a2 + b2*b2)/2.0;
double d = a1*b2 - a2*b1;
return Point(p0.x+(c1*b2-c2*b1)/d,p0.y+(a1*c2-a2*c1)/d);
}
Point o;double r;
inline bool in_cir(const Point &p){
return dcmp(dis(p,o) - r) <= 0;
}
Point p[maxn];int n;
inline void getMinCir(){
o = Point(0,0);r = 0;
for(int i=2;i<=n;++i){
if(!in_cir(p[i])){ o = p[i];r = 0;
for(int j=1;j<i;++j){
if(!in_cir(p[j])){o = (p[i]+p[j])/2.0;r = dis(p[i],o);
for(int k=1;k<j;++k){
if(!in_cir(p[k])){
o = getPoint(p[i],p[j],p[k]);
r = dis(p[i],o);
}
}
}
}
}
}return;
}
Point ch[maxn];int m;
inline void convex(){
sort(p+1,p+n+1);m = 0;
for(int i=1;i<=n;++i){
while(m > 1 && cross(ch[m] - ch[m-1],p[i] - ch[m]) <= 0) -- m;
ch[++m] = p[i];
}int k = m;
for(int i=n-1;i>=1;--i){
while(m > k && cross(ch[m] - ch[m-1],p[i] - ch[m]) <= 0) -- m;
ch[++m] = p[i];
}if(n > 1) -- m;
swap(n,m);swap(p,ch);
}
int main(){
read(n);
for(int i=1;i<=n;++i){
scanf("%lf%lf",&p[i].x,&p[i].y);
}
convex();getMinCir();
printf("%.2lf %.2lf %.2lf
",o.x,o.y,r);
getchar();getchar();
return 0;
}