hdu 4773 Problem of Apollonius

莫名其妙就AC了……

圆的反演……

神马是反演？

快去恶补奥数……

#include<iostream>

#include<map>

#include<string>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<queue>

#include<vector>

#include<algorithm>

using namespace std;

const double pi=acos(-1.0);

const double eps=1e-9;

int dcmp(double x){return fabs(x)<eps?0:x<0?-1:1;}

struct dot

{

    double x,y;

    dot(){}

    dot(double a,double b){x=a;y=b;}

    dot operator +(dot a){return dot(x+a.x,y+a.y);}

    dot operator -(dot a){return dot(x-a.x,y-a.y);}

    dot operator *(double a){return dot(x*a,y*a);}

    double operator *(dot a){return x*a.y-y*a.x;}

    dot operator /(double a){return dot(x/a,y/a);}

    double operator /(dot a){return x*a.x+y*a.y;}

    bool operator ==(dot a){return x==a.x&&y==a.y;}

    void in(){scanf("%lf%lf",&x,&y);}

    void out(){printf("%f %f\n",x,y);}

    dot norv(){return dot(-y,x);}

    dot univ(){double a=mod();return dot(x/a,y/a);}

    dot ro(double a){return dot(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a));}

    double mod(){return sqrt(x*x+y*y);}

    double dis(dot a){return sqrt(pow(x-a.x,2)+pow(y-a.y,2));}

};

struct cir

{

    dot o;

    double r;

    cir(){}

    cir(dot a,double b){o=a;r=b;}

    void in(){o.in();scanf("%lf",&r);}

};

struct seg

{

    dot s,e;

    seg(){}

    seg(dot a,dot b){s=a;e=b;}

};

cir sivs(dot a,dot b,dot c)

{

    dot dir,a1,b1;

    double t,d,w;

    t=fabs((b-a)*(c-a));

    d=a.dis(b);

    t/=d;

    w=0.5/t;

    dir=(b-a).norv();

    a1=c+dir*(w/d);

    b1=c-dir*(w/d);

    if(fabs((b-a)*(a1-a))<fabs((b-a)*(b1-a)))

        return cir(a1,w);

    else

        return cir(b1,w);

}

cir civs(cir a,dot b)

{

    cir c;

    double t,x,y,s;

    t=a.o.dis(b);

    x=1.0/(t-a.r);

    y=1.0/(t+a.r);

    c.r=(x-y)/2.0;

    s=(x+y)/2.0;

    c.o=b+(a.o-b)*(s/t);

    return c;

}

seg se[2];

void comseg(dot a,double r1,dot b,double r2)

{

    double ang;

    ang=acos((r1-r2)/a.dis(b));

    se[0].s=a+(b-a).ro(ang).univ()*r1;

    se[1].s=a+(b-a).ro(-ang).univ()*r1;

    ang=pi-ang;

    se[0].e=b+(a-b).ro(-ang).univ()*r2;

    se[1].e=b+(a-b).ro(ang).univ()*r2;

}

int main()

{

    int T,cnt,i;

    cir a,b,a1,b1,ans[2];

    dot c;

    scanf("%d",&T);

    while(T--)

    {

        a.in();

        b.in();

        c.in();

        a1=civs(a,c);

        b1=civs(b,c);

        comseg(a1.o,a1.r,b1.o,b1.r);

        cnt=0;

        for(i=0;i<2;i++)

            if(dcmp((a1.o-se[i].s)*(se[i].e-se[i].s))==dcmp((c-se[i].s)*(se[i].e-se[i].s)))

                if(dcmp((b1.o-se[i].s)*(se[i].e-se[i].s))==dcmp((c-se[i].s)*(se[i].e-se[i].s)))

					ans[cnt++]=sivs(se[i].s,se[i].e,c);

        printf("%d\n",cnt);

        for(i=0;i<cnt;i++)

            printf("%.8f %.8f %.8f\n",ans[i].o.x,ans[i].o.y,ans[i].r);

    }

}

Problem of Apollonius

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 551    Accepted Submission(s): 124

Special Judge

1

12 10 1 8 10 1 10 10

2

10.00000000 8.50000000 1.50000000

10.00000000 11.50000000 1.50000000

Hint

This problem is special judged.