HDU6242Geometry Problem（随机化）

ゞ浴缸里的玫瑰 2022-05-17 06:58 101阅读 0赞

[传送门][Link 1]

这个题就是随机选三个点，求外心，一开始外心求错了，一直T（因为找不到正确答案），TT

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    int n;
    struct Point{
        double x, y;
    }p[N], p0;
    double r0;
    inline Point operator - (const Point& a, const Point& b){
        return (Point){a.x-b.x, a.y-b.y};
    }
    inline double operator *(const Point& a, const Point& b){
        return a.x*b.x+a.y*b.y;
    }
    inline Point operator * (const Point& a, double b){
        return (Point){a.x*b, a.y*b};
    }
    inline Point operator +(const Point& a, const Point& b){
        return (Point){a.x+b.x, a.y+b.y};
    }
    inline double dis(Point a, Point b){
        return sqrt((a-b)*(a-b));
    }
    inline double Cross(Point a, Point b){
        return a.x*b.y-a.y*b.x;
    }
    inline int dcmp(double x){
        if(fabs(x)<1e-6) return 0;
        return x<0?-1:1;
    }
    
    Point waixin(Point& t1, Point& t2, Point& t3){
        Point v1=t2-t1, v2=t3-t1;
        Point m1=(Point){(t1.x+t2.x)/2, (t1.y+t2.y)/2}, m2={(t3.x+t1.x)/2, (t3.y+t1.y)/2};
        Point v3=m1-m2;
        swap(v1.x, v1.y); swap(v2.x, v2.y);
        v1.x=-v1.x, v2.x=-v2.x;
        double t=Cross(v2, v3)/Cross(v1, v2);
        return m1+v1*t;
    }
    
    bool check(){
        int cnt=0;
        int up=(n+1)/2;
        for(int i=0; i<n; i++){
            if(dcmp(dis(p[i], p0)-r0)==0) cnt++;
            if(cnt>=up) return true;
        }
        return false;
    }
    
    int main(){
        int T;
        scanf("%d", &T);
        while(T--){
            scanf("%d", &n);
            for(int i=0; i<n; i++)
                scanf("%lf%lf", &p[i].x, &p[i].y);
    
            if(n==1){
                printf("%f %f %f\n", p[0].x+1, p[0].y, 1.0);
                continue;
            }
            else if(n<=4){
                Point t={(p[0].x+p[1].x)/2, (p[0].y+p[1].y)/2};
                printf("%f %f %f\n", t.x, t.y, dis(t, p[0]));
                continue;
            }
    
            while(1){
                int t1, t2, t3;
                t1=rand()%n, t2=rand()%n, t3=rand()%n;
                if(t1==t2||t2==t3||t1==t3) continue;
                if(dcmp(Cross(p[t1]-p[t2], p[t3]-p[t2]))==0) continue;
    
                p0=waixin(p[t1], p[t2], p[t3]);
                //printf("%d %d %d\n", t1, t2, t3);
                r0=dis(p[t1], p0);
                if(check())
                    break;
            }
            printf("%f %f %f\n", p0.x, p0.y, r0);
        }
    
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6242