結果

問題 No.199 星を描こう
ユーザー codershifth
提出日時 2016-01-10 22:00:41
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,621 bytes
コンパイル時間 1,653 ms
コンパイル使用メモリ 174,584 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-30 03:43:57
合計ジャッジ時間 2,624 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;

template<typename T>
struct Pt {
    T x, y;
    Pt(T x0, T y0) : x(x0), y(y0) {}
    Pt() :x(0),y(0) {}

    const Pt operator+(const Pt &other) const { return Pt(x+other.x, y+other.y); }
    const Pt operator-(const Pt &other) const { return Pt(x-other.x, y-other.y); }
    Pt &operator+=(const Pt &other) { x += other.x; y += other.y; return *this; }
    Pt &operator-=(const Pt &other) { x -= other.x; y -= other.y; return *this; }
    Pt operator*(double r) const { return Pt(x*r, y*r); }
    bool operator<(const Pt &other) const { return (x < other.x)? true : ((x==other.x)? (y < other.y) : false); }
    bool operator<=(const Pt &other) const { return (*this == other)? true : (*this < other); }
    bool operator>(const Pt &other) const { return (other < *this); }
    bool operator>=(const Pt &other) const { return (other <= *this); }
    bool operator==(const Pt &other) const { return (x==other.x && y==other.y); }
    bool operator!=(const Pt &other) const { return !(operator==(other)); }
    double norm(void) const { return hypot(x, y); }

    // class method
    static double cross(const Pt &a, const Pt &b) { return ((double)a.y*b.x - (double)a.x*b.y); }
    static double dot(const Pt &a, const Pt &b)   { return (double)a.x*b.x+(double)a.y*b.y; }
    friend std::ostream &operator<<(std::ostream &os, const Pt &p) {
            os <<"("<<p.x<<","<<p.y<<")";
            return os;
    }
    // a1,a2を端点とする線分とb1,b2を端点とする線分の交差判定
    static bool intersect(Pt a1, Pt a2, Pt b1, Pt b2) {
            return ( cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) < DBL_EPSILON ) &&
                ( cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1) < DBL_EPSILON );
    }
    static int ccw(const Pt &a, const Pt &b) {
            double area = cross(a, b);
            if (area > 0) return 1;  // counter clockwise
            if (area < 0) return -1; // clockwise
            return 0;                // on line
    }
};
template<typename T>
Pt<T> operator*(double r, const Pt<T> &p) { return p*r; }

typedef Pt<double> Ptd;

class WriteStars {
public:
    void solve(void) {
            vector<Ptd> verts(5);
            REP(i,5)
            {
                int x,y;
                cin>>x>>y;
                verts[i] = Ptd(x,y);
            }

            sort(RANGE(verts));
            // O(5!*5*5)
            do {
                vector<pair<Ptd,Ptd>> edges;
                REP(i,5)
                    edges.push_back(make_pair(verts[i], verts[(i+1)%5]));

                int cnt = 0;
                REP(i,5)
                {
                    auto e = edges[i];
                    Ptd p1,p2;
                    tie(p1,p2) = e;

                    set<Ptd> left;
                    set<Ptd> right;
                    REP(j,5)
                    {
                        if (i == j)
                            continue;

                        Ptd q1,q2;
                        tie(q1,q2) = edges[j];

                        if (p1 == q1 || p1 == q2 || p2 == q1 || p2 == q2)
                            continue;

                        // 線分 e と交差するもののうち端点を left/right に振り分ける
                        if ( !Ptd::intersect(p1,p2,q1,q2) )
                            continue;

                        int ccw1 = Ptd::ccw(p2-p1,q1-p1);
                        int ccw2 = Ptd::ccw(p2-p1,q2-p1);

                        if ( ccw1 == 0 || ccw2 == 0 )
                            continue;

                        if ( ccw1 > 0 )
                        {
                            left.insert(q1);
                            right.insert(q2);
                        }
                        else
                        {
                            left.insert(q2);
                            right.insert(q1);
                        }
                    }
                    if (left.size() == 1 || right.size() == 1)
                        ++cnt;
                }
                if (cnt == 5)
                {
                    cout<<"YES"<<endl;
                    return;
                }
            } while(next_permutation(RANGE(verts)));
            cout<<"NO"<<endl;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new WriteStars();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0