結果
問題 |
No.3005 トレミーの問題
|
ユーザー |
|
提出日時 | 2025-01-17 22:32:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 5,081 bytes |
コンパイル時間 | 2,785 ms |
コンパイル使用メモリ | 201,596 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2025-01-17 22:34:37 |
合計ジャッジ時間 | 3,619 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#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"; }