No.199 星を描こう

No.199 星を描こう - yukicoder

• 星を一筆書きするとみなして、辺を順列で表現して、一つの辺にたいして接続しない残りの２辺が条件を満たすかチェックすれば良い。

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]));

                bool ok = true;
                REP(i,5)
                {
                    auto e = edges[i];
                    Ptd p1,p2;
                    tie(p1,p2) = e;

                    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 とまじわっていればよい
                        if ( !Ptd::intersect(p1,p2,q1,q2) )
                        {
                            ok = false;
                            break;
                        }
                    }
                }
                if (ok)
                {
                    cout<<"YES"<<endl;
                    return;
                }
            } while(next_permutation(RANGE(verts)));
            cout<<"NO"<<endl;
    }
};

• convex hull を使う想定解法がステキ。

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

            auto pts = Ptd::convex_hull(verts);
            if (pts.size() == 5)
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
    }