結果

問題 No.199 星を描こう
コンテスト
ユーザー paruki
提出日時 2016-08-20 18:03:20
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,895 bytes
コンパイル時間 2,224 ms
コンパイル使用メモリ 175,716 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-30 03:51:05
合計ジャッジ時間 3,426 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

#define EPS 1e-8
class V2{
public:
    double x, y;

    V2(){}
    V2(double x_, double y_):x(x_),y(y_){}

    bool operator<(const V2 &p) const{
        return x!=p.x?x<p.x:y<p.y;
    }
    V2 operator+(V2 p) const{
        return V2(add(x,p.x), add(y,p.y));
    }
    V2 operator-(V2 p) const{
        return V2(add(x,-p.x), add(y,-p.y));
    }
    double dist()const{
        return sqrt(x*x+y*y);
    }
private:
    double add(double a, double b)const{
        return abs(a+b)<EPS*(abs(a)+abs(b))?0:a+b;
    }
};
V2 operator *(double k, V2 p){
    p.x *= k;
    p.y *= k;
    return p;
}
double dot(const V2 & a, const V2 &b){
    return a.x*b.x + a.y*b.y;
}
double cross(const V2 &a, const V2 &b){
    return a.x * b.y - a.y * b.x;
}

int ccw(V2 a, V2 b, V2 c) {
    b = b-a; c = c-a;
    if(cross(b, c) > EPS) return +1;
    if(cross(b, c) < -EPS) return -1;
    if(dot(b, c) < -EPS) return +2;
    if (b.dist() < c.dist()) return -2;
    return 0;
}

bool colSegSeg2(const V2 &a, const V2 &b, const V2 &c, const V2 &d){
    bool res = ccw(a,b,c)*ccw(a,b,d) <= 0;
    res &= ccw(c,d,a)*ccw(c,d,b) <= 0;
    return res;
}

double distSegPt(const V2 &a, const V2 &b, const V2 &p){
    V2 ab=b-a, ap=p-a, ba=a-b, bp=p-b;
    if(dot(ab, ap) < EPS) return ap.dist();
    if(dot(ba, bp) < EPS) return bp.dist();
    else return abs(cross(ab, ap) / ab.dist());
}

const int N = 5;

bool check(vector<pii> P){
    auto f = [&](int i){
        return V2(P[i].first, P[i].second);
    };

    rep(i, N){
        V2 a = f(i), b = f((i + 1) % N);
        V2 p, q, r;
        p = f((i + 2) % N);
        q = f((i + 3) % N);
        r = f((i + 4) % N);

        if(!colSegSeg2(a, b, p, q))return false;
        if(!colSegSeg2(a, b, q, r))return false;

        if(distSegPt(p, q, a) < EPS)return false;
        if(distSegPt(p, q, b) < EPS)return false;
        if(distSegPt(q, r, a) < EPS)return false;
        if(distSegPt(q, r, b) < EPS)return false;
    }
    return true;
}

int main(){
    vector<pii> P(N);
    while(cin >> P[0].first >> P[0].second){
        rep(i, N-1)cin >> P[i + 1].first >> P[i + 1].second;
        sort(all(P));

        bool ok = false;
        do{
            if(check(P)){
                ok = true;
                break;
            }
        } while(next_permutation(all(P)));

        if(ok)cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}
0