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

今天药忘吃喽~ 2023-06-01 11:15 72阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=6242][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代码：

1 #include<bits/stdc++.h>
      2 using namespace std;
      3 const double eps = 1e-4;
      4 const double INF = 1e18;
      5 const int maxn = 1e5 + 5;
      6 int sgn(double x)
      7 {
      8     if(fabs(x) < eps) return 0;
      9     else return x < 0 ? -1 : 1;
     10 }
     11 struct Point{
     12     double x, y;
     13     Point(){}
     14     Point(double _x, double _y){
     15         x = _x; y = _y;
     16     }
     17     void input()
     18     {
     19         scanf("%lf %lf", &x, &y);
     20     }
     21     bool operator ==(const Point &b) const{
     22         return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
     23     }
     24     bool operator <(const Point &b) const{
     25         return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;
     26     }
     27     Point operator -(const Point &b) const{
     28         return Point(x - b.x, y - b.y);
     29     }
     30     Point operator +(const Point &b) const{
     31         return Point(x + b.x, y + b.y);
     32     }
     33     double operator ^(const Point &b) const{
     34         return x*b.y - b.x*y;
     35     }
     36     double operator *(const Point &b) const{
     37         return x*b.x + y*b.y;
     38     }
     39     Point operator*(const double &k)const{
     40         return Point(x*k,y*k);
     41     }
     42     Point operator/(const double &k)const{
     43         return Point(x/k,y/k);
     44     }
     45     Point rotleft(){
     46         return Point(-y, x);
     47     }
     48     double distance(Point p)
     49     {
     50         return hypot(x - p.x,y - p.y);
     51     }
     52 } p[maxn];
     53 struct Line{
     54     Point s, e;
     55     Line(){}
     56     Line(Point _s, Point _e){
     57         s = _s, e = _e;
     58     }
     59     Point crosspoint(Line v){
     60         double a1 = (v.e - v.s) ^ (s - v.s);
     61         double a2 = (v.e - v.s) ^ (e - v.s);
     62         return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
     63     }
     64 };
     65 struct circle{
     66     Point p;
     67     double r;
     68     circle(){}
     69     circle(Point a, Point b, Point c){
     70         Line u = Line( (a + b) / 2, ( (a + b) / 2) + ( (b - a).rotleft() ));
     71         Line v = Line( (b + c) / 2, ( (b + c) / 2) + ( (c - b).rotleft() ));
     72         p = u.crosspoint(v);
     73         r = p.distance(a);
     74     }
     75     int relation(Point b){
     76         double dst = b.distance(p);
     77         if(sgn(dst - r)<0) return 2;
     78         else if(sgn(dst - r) == 0) return 1;
     79         return 0;
     80     }
     81 };
     82 int main()
     83 {
     84     int t;
     85     scanf("%d",&t);
     86     srand((int)time(0));
     87     while(t--)
     88     {
     89         int n;
     90         scanf("%d",&n);
     91         for(int i = 0;i < n;i++) p[i].input();
     92         if(n == 1) printf("0.000 0.000 %.6f\n",p[0].distance(Point(0,0)));
     93         else if(n >= 2 && n < 5){
     94             Point v = (p[0] + p[1])/2;
     95             printf("%.6f %.6f %.6f\n", v.x, v.y, 0.5*p[0].distance(p[1]));
     96         }
     97         else{
     98             while(1){
     99                 int a = rand() % n, b = a, c = a;
    100                 while(b = rand() % n){
    101                     if(b != a) break;
    102                 }
    103                 while(c = rand() % n){
    104                     if(c != a && c != b) break;
    105                 }
    106                 circle C = circle(p[a], p[b], p[c]);
    107                 int num = 0;
    108                 for(int i = 0;i < n;i++)
    109                 {
    110                     if(C.relation(p[i]) == 1) num++;
    111                 }
    112                 if(num >= (n + 1) / 2){
    113                     printf("%.6f %.6f %.6f\n",C.p.x ,C.p.y, C.r);
    114                     break;
    115                 }
    116             }
    117         }
    118     }
    119     return 0;
    120 }

转载于:https://www.cnblogs.com/Carered/p/11568666.html

[http_acm.hdu.edu.cn_showproblem.php_pid_6242]: http://acm.hdu.edu.cn/showproblem.php?pid=6242