#1035962 (C++17) No.3005 トレミーの問題

• 問題: No.3005 トレミーの問題
• ユーザー: GOTKAKO
• 提出日時: 2025-01-17 22:32:29
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 5,081 bytes
• コンパイル時間: 1,056 ms
• コンパイル使用メモリ: 203,632 KB
• 最終ジャッジ日時: 2026-06-16 23:24:40
• 合計ジャッジ時間: 1,947 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_1

コンパイルメッセージ

main.cpp: In member function '__int128 frac::gcd128(__int128, __int128)':
main.cpp:20:30: error: call of overloaded 'abs(__int128&)' is ambiguous
   20 |         if(b == 0) return abs(a);
      |                           ~~~^~~
main.cpp:20:30: note: there are 9 candidates
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/cstdlib:83,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/x86_64-pc-linux-gnu/bits/stdc++.h:41,
                 from main.cpp:1:
/usr/include/stdlib.h:980:12: note: candidate 1: 'int abs(int)'
  980 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/cstdlib:87:
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/std_abs.h:85:3: note: candidate 2: 'constexpr long double std::abs(long double)'
   85 |   abs(long double __x)
      |   ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/std_abs.h:81:3: note: candidate 3: 'constexpr float std::abs(float)'
   81 |   abs(float __x)
      |   ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/std_abs.h:77:3: note: candidate 4: 'constexpr double std::abs(double)'
   77 |   abs(double __x)
      |   ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/std_abs.h:67:3: note: candidate 5: 'long long int std::abs(long long int)'
   67 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/std_abs.h:62:3: note: candidate 6: 'long int std::abs(long int)'
   62 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
main.cpp:21:23: error: call of overloaded 'abs(__int128&)' is ambiguous
   21 |         return gcd(abs(a),abs(b));
      |                    ~~~^~~
main.cpp:21:23: note: there are 9 candidates
/usr/include/stdlib.h:980:12: note: candidate 1: 'int 

ソースコード

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

struct frac{ //最終的に分子分母64bitに収まる計算のみ.
    public:
    long long n,d;
    frac() : n(0),d(1){}
    frac(long long v) : n(v),d(1) {}
    frac(__int128_t a,__int128_t b,bool redu = true){
        assert(b != 0);
        if(redu) reduce(a,b);
        n = a,d = b; 
    }
    private:
    __int128_t gcd(__int128_t a,__int128_t b){
        if(a%b == 0) return b;
        return gcd(b,a%b);
    } 
    __int128_t gcd128(__int128_t a,__int128_t b){ //絶対値gcd128.
        if(b == 0) return abs(a);
        return gcd(abs(a),abs(b));
    }
    void reduce(__int128_t &a,__int128_t &b){ //約分.
        if(b < 0) a = -a,b = -b;
        __int128_t div = gcd128(a,b);
        a /= div; b /= div;
    }
    public:
    //計算量 O(logmax(d,b.d)).
    friend frac operator+(const frac &b){return b;}
    friend frac operator-(const frac &b){return frac(-b.n,b.d,false);}
    friend frac operator+(const frac &a,const frac &b){
        return frac((__int128_t)a.n*b.d+(__int128_t)b.n*a.d,(__int128_t)a.d*b.d);
    } 
    friend frac operator-(const frac &a,const frac &b){
        return frac((__int128_t)a.n*b.d-(__int128_t)b.n*a.d,(__int128_t)a.d*b.d);
    }
    friend frac operator*(const frac &a,const frac &b){
        long long g1 = std::gcd(a.n,b.d),g2 = std::gcd(a.d,b.n);
        return frac((a.n/g1)*(b.n/g2),(a.d/g2)*(b.d/g1),false);
    }
    friend frac operator/(const frac &a,const frac &b){
        assert(b.n != 0);
        long long g1 = std::gcd(a.n,b.n),g2 = std::gcd(a.d,b.d);
        if(b.n < 0) return frac((-a.n/g1)*(b.d/g2),(a.d/g2)*(-b.n/g1));
        else return frac((a.n/g1)*(b.d/g2),(a.d/g2)*(b.n/g1));
    }
    friend bool operator==(const frac &a,const frac &b){return a.n==b.n && a.d==b.d;}
    friend bool operator!=(const frac &a,const frac &b){return a.n!=b.n || a.d!=b.d;}
    friend bool operator>(const frac &a,const frac &b){return (__int128_t)a.n*b.d > (__int128_t)b.n*a.d;}
    friend bool operator>=(const frac &a,const frac &b){return (__int128_t)a.n*b.d >= (__int128_t)b.n*a.d;}
    friend bool operator<(const frac &a,const frac &b){return (__int128_t)a.n*b.d < (__int128_t)b.n*a.d;}
    friend bool operator<=(const frac &a,const frac &b){return (__int128_t)a.n*b.d <= (__int128_t)b.n*a.d;}
 
    frac &operator=(const frac &b) = default;
    frac operator+=(const frac &b){return *this=*this+b;}
    frac operator-=(const frac &b){return *this=*this-b;}
    frac operator*=(const frac &b){return *this=*this*b;}
    frac operator/=(const frac &b){return *this=*this/b;}
    frac operator++(int){*this += frac(1); return *this;}
    frac operator--(int){*this -= frac(1); return *this;}
 
    double decimal(){return (n+0.0)/d;}
    long double decimall(){return ((long double)n)/d;}
    long long num(){return n;} long long den(){return d;}
    long long floor(){return n<0?(n+1)/d-1:n/d;}
    long long ceil(){return n>0?(n-1)/d+1:n/d;}
    frac inv(){return frac(n>=0?d:-d,n>=0?n:-n,false);}
};
struct Point{
    frac x,y;
    Point() : x(0),y(0) {}
    Point(long long a,long long b) : x(frac(a)),y(frac(b)) {}
    Point(frac a,frac b) : x(a),y(b) {}
    Point operator+(const Point &b){return Point(x+b.x,y+b.y);}
    Point operator-(const Point &b){return Point(x-b.x,y-b.y);}
    Point operator+=(const Point &b){return *this=*this+b;}
    Point operator-=(const Point &b){return *this=*this-b;}
    bool operator==(const Point &b){return x==b.x && y==b.y;}
    bool operator!=(const Point &b){return x!=b.x || y!=b.y;}

    friend frac dist(const Point &a,const Point &b){
        return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    }
};
long long INF = 8e18;
frac cross(Point &a,Point &b){return a.x*b.y-a.y*b.x;}
Point findInt/*ersecton*/(Point &a,Point &b,Point &c,Point &d){//線分abと線分cdの交点.
    Point NG(INF,INF);
    Point ba = b-a,dc = d-c,ca = c-a,ac = a-c;
    frac div = cross(ba,dc);
    if(div == 0) return NG;
    frac s = cross(ca,dc)/div;
    frac t = cross(ba,ac)/div;
    if(s < 0 || s > 1 || t < 0 || t > 1) return NG;
if(s <= 0 || s >= 1 || t <= 0 || t >= 1) return NG; //端点NG.
    return Point{a.x+s*ba.x,a.y+s*ba.y};
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N = 4;
    vector<Point> P(4);
    for(auto &p : P){
        int x,y; cin >> x >> y;
        p = {x,y};
    }

    bool yes = false;
    Point c = findInt(P.at(0),P.at(1),P.at(2),P.at(3));
    frac one = dist(c,P.at(0)),two = dist(c,P.at(1)),three = dist(c,P.at(2)),four = dist(c,P.at(3));
    if(c.x != INF && one*two == three*four) yes = true;
    c = findInt(P.at(0),P.at(3),P.at(1),P.at(2));
    one = dist(c,P.at(0)),two = dist(c,P.at(1)),three = dist(c,P.at(2)),four = dist(c,P.at(3));
    if(c.x != INF && one*four == two*three) yes = true;
    c = findInt(P.at(0),P.at(2),P.at(1),P.at(3));
    one = dist(c,P.at(0)),two = dist(c,P.at(1)),three = dist(c,P.at(2)),four = dist(c,P.at(3));
    if(c.x != INF && one*three == two*four) yes = true;
    
    if(yes) cout << "YES\n";
    else cout << "NO\n";
}