結果

問題 No.199 星を描こう
コンテスト
ユーザー はまやんはまやん
提出日時 2016-06-11 16:35:14
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,554 bytes
コンパイル時間 2,099 ms
コンパイル使用メモリ 175,532 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-30 03:49:52
合計ジャッジ時間 2,873 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)




const double EPS = 1e-8;
const double INF = 1e12;
typedef complex<double> P;
namespace std {
	bool operator < (const P& a, const P& b) {
		return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
	}
}
double cross(const P& a, const P& b) {
	return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {
	return real(conj(a)*b);
}

struct L : public vector<P> {
	L() {}
	L(const P &a, const P &b) {
		push_back(a); push_back(b);
	}
};

typedef vector<P> G;



int ccw(P a, P b, P c) {
	b -= a; c -= a;
	if (cross(b, c) > 0)   return +1;       // counter clockwise
	if (cross(b, c) < 0)   return -1;       // clockwise
	if (dot(b, c) < 0)     return +2;       // c--a--b on line
	if (norm(b) < norm(c)) return -2;       // a--b--c on line
	return 0;
}

G convex_hull(vector<P> ps) {
	int n = ps.size(), k = 0;
	sort(ps.begin(), ps.end());
	G ch(2 * n);
	for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
		while (k >= 2 && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
	for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = ps[i--]) // upper-hull
		while (k >= t && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
	ch.resize(k - 1);
	return ch;
}



int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	double x, y;
	vector<P> ps(5);
	while (cin >> x >> y)
	{
		ps[0] = P(x, y);
		rep(i, 1, 5)
		{
			cin >> x >> y;
			ps[i] = P(x, y);
		}

		G cv = convex_hull(ps);

		if (cv.size() == 5)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	

}
0