h_nosonの日記

競プロ、CTFなど

yukicoder No.199 星を描こう

問題
No.199 星を描こう - yukicoder
XY座標上の点が5つ与えられる.点を線で繋いで星が描けるかどうかを判定する.

解法1
それぞれの頂点を結ぶ線分をすべて考えて,
他の線分と交わる回数が2回のものが5つあれば星を描ける(端は数えません).
f:id:h_noson:20160428215600p:plain
交点の求め方
2つの線分p1-p2,q1-q2の交点を求めるために
まず直線p1-p2上の点をtを使って表すと,
p1+t(p2-p1)
この点が直線q1-q2上にある条件は,外積=0より
(q2-q1)\times(p1+t(p2-p1)-q1)=0
tを求めることにより交点は
x=p1+\frac{(q2-q1)\times(p1-q1)}{(q2-q1)\times(p2-p1)}(p2-p1)
で与えられる.
xは直線p1-p2,q1-q2上にいることが約束されている.
次に線分の範囲に点があることを内積を使って示す.
ベクトルa,bの間にベクトルcがあることは
(a-c)\cdot (a-b)\leq0
を満たすことに等しい.よって
(p1-x)\cdot (p2-x)\leq0\text{ かつ }(q1-x)\cdot (q2-x)\leq0
を満たせば交点が存在したことになる.

解法2
凸包を考える.
囲む多角形が五角形なら星を描ける.
f:id:h_noson:20160428220020p:plain
四角形などになると頂点が引っ込んでしまい星を作れない.
f:id:h_noson:20160428220554p:plain

ソースコード1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP(i,n,0)
#define REP(i,s,e) for (i = s; i < e; i++)
#define rep(i,n) REP(i,0,n)
#define INF 100000000

typedef long long ll;
typedef pair<double,double> P;

double dot(P p, P q) {
    return p.first * q.first + p.second * q.second;
}

double det(P p, P q) {
    return p.first * q.second - p.second * q.first;
}

P operator +(P p, P q) {
    return make_pair(p.first+q.first,p.second+q.second);
}

P operator -(P p, P q) {
    return make_pair(p.first-q.first,p.second-q.second);
}

P operator *(double s, P p) {
    return make_pair(p.first*s,p.second*s);
}

int main() {
    int i, j, k, l, cnt;
    P p[5];
    rep (i,5) {
        double x, y;
        cin >> x >> y;
        p[i] = make_pair(x,y);
    }
    cnt = 0;
    rep (i,4) REP (j,i+1,5) {
        int cross = 0;
        rep (k,5) REP (l,k+1,5) {
            if (k != i && k != j && l != i && l != j && det(p[j]-p[i],p[l]-p[k]) != 0) {
                double t = det(p[l]-p[k],p[k]-p[i])/det(p[l]-p[k],p[j]-p[i]);
                auto q = p[i] + t*(p[j]-p[i]);
                if (dot(p[i]-q,p[j]-q) < 0 && dot(p[k]-q,p[l]-q) < 0)
                    cross++;
            }
        }
        if (cross != 0 && cross != 2) {
            cout << "NO" << endl;
            return 0;
        }
        if (cross == 2) cnt++;
    }
    if (cnt == 5)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

ソースコード2

#include <iostream>
#include <algorithm>
using namespace std;

typedef pair<int,int> P;

int det(P a, P b) {
    return a.first * b.second - a.second * b.first;
}

P operator-(P a, P b) {
    return make_pair(a.first-b.first,a.second-b.second);
}

bool cmp(P a, P b) {
    if (a.first == b.first)
        return a.second > b.second;
    else
        return a.first < b.first;
}

int main() {
    int i, k, t;
    P p[5], out[5];
    for (i = 0; i < 5; i++) {
        int x, y;
        cin >> x >> y;
        p[i] = make_pair(x,y);
    }
    sort(p,p+5,cmp);
    k = 0;
    for (i = 0; i < 5; i++) {
        while (k > 1 && det(out[k-1]-out[k-2],p[i]-out[k-1]) <= 0) k--;
        out[k++] = p[i];
    }
    for (i = 4, t = k; i >= 0; i--) {
        while (k > t && det(out[k-1]-out[k-2],p[i]-out[k-1]) <= 0) k--;
        out[k++] = p[i];
    }
    k--;
    if (k == 5)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}