hdu 6206 : Apple 【计算几何 + 分数类】

题目链接

比赛时C++上__float128都被卡精度，然后扔给队友用Java的BigDecimal过了

算法不多说，求三角形外心可以参考 维基百科 https://zh.wikipedia.org/wiki/%E5%A4%96%E6%8E%A5%E5%9C%93

这里用到了分数类。根据算法中涉及到的各处细节可以发现，这道题可以满足条件：①只涉及到有理数运算；②有理数用分数表示时，分子分母均不超过1e(12*3)=1e36级别。故，我们可以把原先用浮点数来表示的数据，改成用分数类表示，具体实现可以见代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

struct frac
{
    __int128 p,q;
    frac(){}
    frac(__int128 _p,__int128 _q)
    {
        if(_q<0) _p=-_p,_q=-_q;
        p=_p,q=_q;
    }
    frac operator +(const frac&rhs)
    {
        __int128 a,b;
        b=q*rhs.q;
        a=p*rhs.q+q*rhs.p;
        if(b==0) return frac(0,1);
        __int128 g=__gcd(a,b);
        a/=g;
        b/=g;
        return frac(a,b);
    }
    frac operator -(const frac&rhs)
    {
        __int128 a,b;
        b=q*rhs.q;
        a=p*rhs.q-q*rhs.p;
        if(b==0) return frac(0,1);
        __int128 g=__gcd(a,b);
        a/=g;
        b/=g;
        return frac(a,b);
    }
    frac operator *(const frac&rhs)
    {
        __int128 a,b;
        b=q*rhs.q;
        a=p*rhs.p;
        if(b==0) return frac(0,1);
        __int128 g=__gcd(a,b);
        a/=g;
        b/=g;
        return frac(a,b);
    }
    frac operator /(const frac&rhs)
    {
        __int128 a,b;
        b=q*rhs.p;
        a=p*rhs.q;
        if(b==0) return frac(0,1);
        __int128 g=__gcd(a,b);
        a/=g;
        b/=g;
        return frac(a,b);
    }
    bool operator <(const frac&rhs)const
    {
        return p*rhs.q<rhs.p*q;
    }
    bool operator >(const frac&rhs)const
    {
        return p*rhs.q>rhs.p*q;
    }
    bool operator ==(const frac&rhs)const
    {
        return !(p*rhs.q<rhs.p*q)&&!(p*rhs.q>rhs.p*q);
    }
};

struct Point
{
    frac x,y;
    void read()
    {
        LL t1,t2;
        cin>>t1>>t2;
        x=frac((__int128)t1,1),y=frac((__int128)t2,1);
    }
    Point(){}
    Point(frac _x,frac _y)
    {
        x=_x,y=_y;
    }
    Point operator -(const Point& rhs)
    {
        return Point(x-rhs.x,y-rhs.y);
    }
};
typedef Point Vector;

frac Dot(Vector A,Vector B)
{
    return A.x*B.x+A.y*B.y;
}

Point waixin(Point a,Point b,Point c) {  
    frac a1 = b.x - a.x, b1 = b.y - a.y, c1 = (a1*a1 + b1*b1)/frac(2,1);  
    frac a2 = c.x - a.x, b2 = c.y - a.y, c2 = (a2*a2 + b2*b2)/frac(2,1);  
    frac d = a1*b2 - a2*b1;  
    return Point(a.x + (c1*b2 - c2*b1)/d, a.y + (a1*c2 -a2*c1)/d);  
}  
Point p1,p2,p3,c,p;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        p1.read();
        p2.read();
        p3.read();
        c=waixin(p1,p2,p3);
        p.read();
        if(Dot(p-c,p-c)>Dot(p1-c,p1-c))
            puts("Accepted");
        else
            puts("Rejected");
    }
}