【BZOJ-1336&1337】Alie最小圆覆盖最小圆覆盖（随机增量法）-白红宇

【BZOJ-1336&1337】Alie最小圆覆盖最小圆覆盖（随机增量法）

阅读量：5360 次

发布时间：2019-06-15

本文共 1897 字，大约阅读时间需要 6 分钟。

1336: [Balkan2002]Alien最小圆覆盖

Time Limit: 1 Sec Memory Limit: 162 MBSec Special Judge

Submit: 1573 Solved: 697

[][][]

Description

给出N个点，让你画一个最小的包含所有点的圆。

Input

先给出点的个数N,2<=N<=100000，再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)

Output

输出圆的半径，及圆心的坐标

Sample Input

8.0 9.0

4.0 7.5

1.0 2.0

5.1 8.7

9.0 2.0

4.5 1.0

Sample Output

5.00

5.00 5.00

HINT

Source

1337: 最小圆覆盖

Time Limit: 1 Sec Memory Limit: 64 MB

Submit: 897 Solved: 437

[][][]

Description

给出平面上N个点,N<=10^5.请求出一个半径最小的圆覆盖住所有的点

Input

第一行给出数字N，现在N行，每行两个实数x,y表示其坐标.

Output

输出最小半径，输出保留三位小数.

Sample Input

1 0

0 1

0 -1

-1 0

Sample Output

1.000

HINT

Source

Solution

最小圆覆盖裸题，随机增量法

这道题有个需要注意的地方，输出的时候不要只输出2位小数，可能会WA，可以考虑直接输出

直接把课件黏上来= =

Code

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define INF 1000000000#define fi first#define se second#define N 100005#define MP(x,y) make_pair(x,y)using namespace std;typedef long long LL;typedef pair
                   
                     pii;typedef long double Double;struct Vector{ double x,y; Vector(double X=0,double Y=0) {x=X,y=Y;}};typedef Vector Point;typedef vector
                    
                      Polygon;const double eps=1e-12;const double pi=acos(-1.0);struct Line{ Point P; Vector v; double ang; Line() {} Line(Point P,Vector v):P(P),v(v) {ang=atan2(v.y,v.x);} bool operator<(const Line &L) const { return ang
                     
                      0) { c=p[i],r=0; for(j=0;j
                      
                       0) { c=(p[i]+p[j])/2; r=Len(c-p[i]); for(k=0;k
                       
                        0) { c=Center_of_gravity(p[i],p[j],p[k]); r=Len(c-p[i]); } } } return r;}#define MAXN 100010Point Po[MAXN];int main(){ srand(20000104); int n; scanf("%d",&n); for (int i=1; i<=n; i++) { double x,y; scanf("%lf%lf",&x,&y); Po[i-1]=Point(x,y); } Point c; printf("%lf\n",Min_Cover_Circle(Po,n,c)); printf("%lf %lf",c.x,c.y); return 0;}