[hdu-3007]Buried memory 最小覆盖圆

大致题意：
　　平面上有n个点，求一个最小的圆覆盖住所有点
　　最小覆盖圆裸题
　　学习了一波最小覆盖圆算法
  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<set>
  7 #include<map>
  8 #include<stack>
  9 #include<time.h>
 10 #include<cstdlib>
 11 #include<cmath>
 12 #include<list>
 13 using namespace std;
 14 #define MAXN 100100
 15 #define eps 1e-9
 16 #define For(i,a,b) for(int i=a;i<=b;i++) 
 17 #define Fore(i,a,b) for(int i=a;i>=b;i--) 
 18 #define lson l,mid,rt<<1
 19 #define rson mid+1,r,rt<<1|1
 20 #define mkp make_pair
 21 #define pb push_back
 22 #define cr clear()
 23 #define sz size()
 24 #define met(a,b) memset(a,b,sizeof(a))
 25 #define iossy ios::sync_with_stdio(false)
 26 #define fre freopen
 27 #define pi acos(-1.0)
 28 #define inf 1e6+7
 29 #define Vector Point
 30 const int Mod=1e9+7;
 31 typedef unsigned long long ull;
 32 typedef long long ll;
 33 int dcmp(double x){
 34     if(fabs(x)<=eps) return 0;
 35     return x<0?-1:1;
 36 }
 37 struct Point{
 38     double x,y;
 39     Point(double x=0,double y=0):x(x),y(y) {}
 40     bool operator < (const Point &a)const{
 41         if(x==a.x) return y<a.y;
 42         return x<a.x;
 43     }
 44     Point operator - (const Point &a)const{
 45         return Point(x-a.x,y-a.y);
 46     }
 47     Point operator + (const Point &a)const{
 48         return Point(x+a.x,y+a.y);
 49     }
 50     Point operator * (const double &a)const{
 51         return Point(x*a,y*a);
 52     }
 53     Point operator / (const double &a)const{
 54         return Point(x/a,y/a);
 55     }
 56     void read(){
 57         scanf("%lf%lf",&x,&y);
 58     }
 59     void out(){
 60         cout<<"debug: "<<x<<" "<<y<<endl;
 61     }
 62     bool operator == (const Point &a)const{
 63         return dcmp(x-a.x)==0 && dcmp(y-a.y)==0;
 64     }
 65 };
 66 double Dot(Vector a,Vector b) {
 67     return a.x*b.x+a.y*b.y;
 68 }
 69 double dis(Vector a) {
 70     return sqrt(Dot(a,a));
 71 }
 72 double Cross(Point a,Point b){
 73     return a.x*b.y-a.y*b.x;
 74 }
 75 int n;
 76 Point p[5005];
 77 double r;
 78 Point cp;
 79 bool inCrcle(Point tp){
 80     return dcmp(dis(tp-cp)-r)<=0;
 81 }
 82 void getCrcle(Point a,Point b,Point c){
 83     Point p1=b-a,p2=c-a;
 84     double d=2*Cross(p1,p2);
 85     cp.x=(p2.y*Dot(p1,p1)-p1.y*Dot(p2,p2))/d+a.x;
 86     cp.y=(p1.x*Dot(p2,p2)-p2.x*Dot(p1,p1))/d+a.y;
 87     r=dis(a-cp);
 88 }
 89 void solve(){
 90     For(i,0,n-1) p[i].read();
 91     random_shuffle(p,p+n);
 92     cp=p[0];r=0;
 93     For(i,1,n-1) {
 94         if(!inCrcle(p[i])){
 95             r=0;
 96             cp=p[i];
 97             For(j,0,i-1) {
 98                 if(!inCrcle(p[j])) {
 99                     r=dis(p[j]-p[i])/2;
100                     cp=(p[j]+p[i])/2;
101                     For(k,0,j-1) {
102                         if(!inCrcle(p[k]))
103                             getCrcle(p[i],p[j],p[k]);
104                     }
105                 }
106             }
107         }
108     }
109     printf("%.2lf %.2lf %.2lf
",cp.x,cp.y,r);
110 }
111 int main(){
112 //    fre("in.txt","r",stdin);
113     int t=0;
114     while(~scanf("%d",&n) && n)    solve();
115     return 0;
116 }
View Code