SGU 227 The art to the broad masses!（圆弧求交点）

冷不防 2022-03-28 16:08 185阅读 0赞

题目链接：[http://acm.sgu.ru/problem.php?contest=0&problem=227][http_acm.sgu.ru_problem.php_contest_0_problem_227]

题意：给定一些圆弧。求圆弧的交点。

思路：求出圆心交点。判断交点在不在圆弧内用叉积。

int DB(double x)
    {
        if(x>1e-10) return 1;
        if(x<-1e-10) return -1;
        return 0;
    }
    
    
    class point
    {
    public:
        double x,y;
    
        point(){}
        point(double _x,double _y)
        {
            x=_x;
            y=_y;
        }
    
        void get()
        {
            RD(x,y);
        }
    
        point operator+(point a)
        {
            return point(x+a.x,y+a.y);
        }
    
        point operator-(point a)
        {
            return point(x-a.x,y-a.y);
        }
    
        double operator*(point a)
        {
            return x*a.y-y*a.x;
        }
    
        point operator*(double t)
        {
            return point(x*t,y*t);
        }
    
        double operator^(point a)
        {
            return x*a.x+y*a.y;
        }
    
        double getLen()
        {
            return sqrt(x*x+y*y);
        }
    
        point operator/(double t)
        {
            return point(x/t,y/t);
        }
    
        double getAng(point a)
        {
            return atan2(*this*a,*this^a);
        }
    
        int operator==(const point &a) const
        {
            return DB(x-a.x)==0&&DB(y-a.y)==0;
        }
    
        int operator<(const point &a) const
        {
            if(DB(x-a.x)) return x<a.x;
            return y<a.y;
        }
    
        point adjust(double p)
        {
            point t=*this;
            double x=p/t.getLen();
            return point(x*t.x,x*t.y);
        }
    
        point zhuanNi(double ang)
        {
            return point(x*cos(ang)-y*sin(ang),x*sin(ang)+y*cos(ang));
        }
    
        point zhuanShun(double ang)
        {
            return point(x*cos(ang)+y*sin(ang),-x*sin(ang)+y*cos(ang));
        }
    
        point vertical()
        {
            return point(y,-x);
        }
    
        void print()
        {
            if(DB(x)==0) x=0;
            if(DB(y)==0) y=0;
            printf("%.3lf %.3lf\n",x,y);
        }
    };
    
    const int N=55;
    point p[N][3],O[N];
    vector<point> ans;
    double R[N];
    int n,d[N];
    
    point getCross(point a,point b,point p,point q)
    {
        double s1=(a-p)*(b-p);
        double s2=(b-q)*(a-q);
        return (p*s2+q*s1)/(s1+s2);
    }
    
    int cmp(point a,point b)
    {
        if(DB(a.x-b.x)) return a.x<b.x;
        return a.y<b.y;
    }
    
    point getCenter(point a,point b,point c)
    {
        point M1=(a+b)/2,dir1=(b-a).vertical();
        point M2=(b+c)/2,dir2=(c-b).vertical();
        return getCross(M1,M1+dir1,M2,M2+dir2);
    }
    
    int isInside(point a,int t)
    {
        return DB((p[t][0]-p[t][2])*(a-p[t][2]))*d[t];
    }
    
    
    void judge(int x,int y)
    {
        if(!isInside(p[x][0],y)&&!isInside(p[x][2],y)&&d[x]==d[y])
        {
            puts("Infinity");
            exit(0);
        }
        if(isInside(p[x][0],y)>0||isInside(p[x][2],y)>0||isInside(p[y][0],x)>0||isInside(p[y][2],x)>0)
        {
            puts("Infinity");
            exit(0);
        }
        if(!isInside(p[x][0],y)) ans.pb(p[x][0]);
        if(!isInside(p[x][2],y)) ans.pb(p[x][2]);
    }
    
    void calCross(int x,int y,point &a,point &b)
    {
        double L=(O[x]-O[y]).getLen();
        double ang=(sqr(R[y])+sqr(L)-sqr(R[x]))/(2*R[y]*L);
        ang=acos(ang);
        point A=O[x]-O[y],B;
    
        B=A.zhuanNi(ang);
        B=B.adjust(R[y]);
        a=O[y]+B;
    
        B=A.zhuanShun(ang);
        B=B.adjust(R[y]);
        b=O[y]+B;
    }
    
    void deal()
    {
        int i,j,k,t;
        double L;
        point a,b;
        for(i=1;i<=n;i++) for(j=i+1;j<=n;j++)
        {
            if(O[i]==O[j]&&!DB(R[i]-R[j]))
            {
                judge(i,j);
                continue;
            }
            L=(O[i]-O[j]).getLen();
            if(DB(L-(R[i]+R[j]))>0||DB(L-fabs(R[i]-R[j]))<0) continue;
            calCross(i,j,a,b);
            if(isInside(a,i)>=0&&isInside(a,j)>=0) ans.pb(a);
            if(isInside(b,i)>=0&&isInside(b,j)>=0) ans.pb(b);
        }
    }
    
    int main()
    {
        RD(n);
        int i;
        FOR1(i,n)
        {
            p[i][0].get();
            p[i][2].get();
            p[i][1].get();
            O[i]=getCenter(p[i][0],p[i][1],p[i][2]);
            d[i]=DB((p[i][0]-p[i][2])*(p[i][1]-p[i][2]));
            R[i]=(O[i]-p[i][0]).getLen();
        }
        deal();
        sort(ans.begin(),ans.end(),cmp);
        int S=unique(ans.begin(),ans.end())-ans.begin();
        PR(S);
        for(i=0;i<S;i++) ans[i].print();
        return 0;
    }

[http_acm.sgu.ru_problem.php_contest_0_problem_227]: http://acm.sgu.ru/problem.php?contest=0&problem=227