結果

問題 No.199 星を描こう
ユーザー codershifthcodershifth
提出日時 2016-01-10 22:10:41
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,824 bytes
コンパイル時間 1,662 ms
コンパイル使用メモリ 174,736 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-09 13:54:48
合計ジャッジ時間 2,519 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 1 ms
6,944 KB
testcase_14 AC 1 ms
6,944 KB
testcase_15 AC 2 ms
6,944 KB
testcase_16 AC 2 ms
6,940 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 AC 2 ms
6,944 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 1 ms
6,944 KB
testcase_21 AC 1 ms
6,944 KB
testcase_22 AC 2 ms
6,944 KB
testcase_23 AC 1 ms
6,940 KB
testcase_24 AC 2 ms
6,940 KB
testcase_25 AC 2 ms
6,940 KB
testcase_26 AC 2 ms
6,944 KB
testcase_27 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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) < 0 ) &&
                ( cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1) < 0 );
    }
    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 に振り分ける
                        //       2
                        //   0 --------- 1
                        //      3    4
                        // のように 線分01 と交差する線分の端点が 01 のどちらかに振り分けられていて
                        // その個数が 1 個であればよい
                        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 )
                        {
                            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