题目大意:

给定n个点,求面积最小的园覆盖所有点.其中\(n \leq 10^6\)

题解:

恩。。。

刚拿到这道题的时候...

什么？？？最小圆覆盖不是\(O(n^3)\)的随机增量算法吗？？？？？

\(10^6\)又是个什么鬼？？？？？？？？？

然后去%了popoqqq大爷的题解...原来这道题数据是随机的啊。。。

随机数据有一个性质,在凸包上的点不超过\(logn\)

所以我们求凸包然后在上面跑随机增量算法即可

#include 
    
     #include 
     
      #include 
      
       #include 
       
        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
         -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)\n",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
         
           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\n",o.x,o.y,r); getchar();getchar(); return 0;}