yukicoder No.199 星を描こう
問題
No.199 星を描こう - yukicoder
XY座標上の点が5つ与えられる.点を線で繋いで星が描けるかどうかを判定する.
解法1
それぞれの頂点を結ぶ線分をすべて考えて,
他の線分と交わる回数が2回のものが5つあれば星を描ける(端は数えません).
交点の求め方
2つの線分の交点を求めるために
まず直線上の点をを使って表すと,
この点が直線上にある条件は,外積より
を求めることにより交点は
で与えられる.
は直線上にいることが約束されている.
次に線分の範囲に点があることを内積を使って示す.
ベクトルの間にベクトルがあることは
を満たすことに等しい.よって
を満たせば交点が存在したことになる.
解法2
凸包を考える.
囲む多角形が五角形なら星を描ける.
四角形などになると頂点が引っ込んでしまい星を作れない.
#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; }
#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; }