HDU 6242 Geometry Problem（计算几何 + 随机化）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6242

思路：当 n == 1 时任取一点 p 作为圆心即可。

　　　　n >= 2 && n < 5 时此时有可能出现所有点共线，所以取任意俩点间中点作为圆的圆心。

　　　　n >= 5 保证了有解。所以不可能有所有点共线的情况，随机取三个点在正解圆上的概率是 1/8，还是蛮大的...。

　　　　外学了下随机算法的写法....时间种子 time（0）要强制转成int，不然会WA，不造为啥....

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 const double eps = 1e-;

 const double INF = 1e18;

 const int maxn = 1e5 + ;

 int sgn(double x)

 {

     if(fabs(x) < eps) return ;

     else return x <  ? - : ;

 }

 struct Point{

     double x, y;

     Point(){}

     Point(double _x, double _y){

         x = _x; y = _y;

     }

     void input()

     {

         scanf("%lf %lf", &x, &y);

     }

     bool operator ==(const Point &b) const{

         return sgn(x - b.x) ==  && sgn(y - b.y) == ;

     }

     bool operator <(const Point &b) const{

         return sgn(x - b.x) ==  ? sgn(y - b.y) <  : x < b.x;

     }

     Point operator -(const Point &b) const{

         return Point(x - b.x, y - b.y);

     }

     Point operator +(const Point &b) const{

         return Point(x + b.x, y + b.y);

     }

     double operator ^(const Point &b) const{

         return x*b.y - b.x*y;

     }

     double operator *(const Point &b) const{

         return x*b.x + y*b.y;

     }

     Point operator*(const double &k)const{

         return Point(x*k,y*k);

     }

     Point operator/(const double &k)const{

         return Point(x/k,y/k);

     }

     Point rotleft(){

         return Point(-y, x);

     }

     double distance(Point p)

     {

         return hypot(x - p.x,y - p.y);

     }

 } p[maxn];

 struct Line{

     Point s, e;

     Line(){}

     Line(Point _s, Point _e){

         s = _s, e = _e;

     }

     Point crosspoint(Line v){

         double a1 = (v.e - v.s) ^ (s - v.s);

         double a2 = (v.e - v.s) ^ (e - v.s);

         return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));

     }

 };

 struct circle{

     Point p;

     double r;

     circle(){}

     circle(Point a, Point b, Point c){

         Line u = Line( (a + b) / , ( (a + b) / ) + ( (b - a).rotleft() ));

         Line v = Line( (b + c) / , ( (b + c) / ) + ( (c - b).rotleft() ));

         p = u.crosspoint(v);

         r = p.distance(a);

     }

     int relation(Point b){

         double dst = b.distance(p);

         if(sgn(dst - r)<) return ;

         else if(sgn(dst - r) == ) return ;

         return ;

     }

 };

 int main()

 {

     int t;

     scanf("%d",&t);

     srand((int)time());

     while(t--)

     {

         int n;

         scanf("%d",&n);

         for(int i = ;i < n;i++) p[i].input();

         if(n == ) printf("0.000 0.000 %.6f\n",p[].distance(Point(,)));

         else if(n >=  && n < ){

             Point v = (p[] + p[])/;

             printf("%.6f %.6f %.6f\n", v.x, v.y, 0.5*p[].distance(p[]));

         }

         else{

             while(){

                 int a = rand() % n, b = a, c = a;

                 while(b = rand() % n){

                     if(b != a) break;

                 }

                 while(c = rand() % n){

                     if(c != a && c != b) break;

                 }

                 circle C = circle(p[a], p[b], p[c]);

                 int num = ;

                 for(int i = ;i < n;i++)

                 {

                     if(C.relation(p[i]) == ) num++;

                 }

                 if(num >= (n + ) / ){

                     printf("%.6f %.6f %.6f\n",C.p.x ,C.p.y, C.r);

                     break;

                 }

             }

         }

     }

     return ;

 }

巴特西

HDU 6242 Geometry Problem（计算几何 + 随机化）

最新文章

热门文章