結果

問題 No.199 星を描こう
コンテスト
ユーザー 古寺いろは
提出日時 2015-04-29 00:05:37
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,512 bytes
コンパイル時間 1,628 ms
コンパイル使用メモリ 164,100 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-30 03:17:36
合計ジャッジ時間 2,626 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;


 
long long getS2(long long x1, long long y1, long long x2, long long y2){
	return (x1*y2) - (x2*y1);
}

long long getS(int x1, int y1, int x2, int y2, int x3, int y3){
	return getS2(x2 - x1, y2 - y1, x3 - x1, y3 - y1);
}

double EPS = 1e-9;

class P
{
public:
	int x, y;

	P()
	{

	}

	P(int _x, int _y)
	{
		x = _x;
		y = _y;
	}

	void init(int _x, int _y)
	{
		x = _x;
		y = _y;
	}

	P add(P p)
	{
		return P(x + p.x, y + p.y);
	}

	P sub(P p)
	{
		return P(x - p.x, y - p.y);
	}

	P mul(int m)
	{
		return P(x * m, y * m);
	}

	P div(int d)
	{
		return P(x / d, y / d);
	}

	double abs()
	{
		return sqrt(abs2());
	}

	int abs2()
	{
		return x * x + y * y;
	}

	double arg()
	{
		return atan2(y, x);
	}

	int dot(P p)
	{
		return x * p.x + y * p.y;
	}

	int det(P p)
	{
		return x * p.y - y * p.x;
	}

	double ang(P p)
	{
		return atan2(det(p), dot(p));
	}

	P rot90()
	{
		return P(y, -x);
	}


	static double rad(P u, P v)
	{
		double rad = atan2(u.det(v), u.dot(v));
		if (rad < -EPS) rad += 2 * 3.141592653589793238462;
		return rad;
	}
};

static int sig(double x){
	if (x > 0) return 1;
	if (x < 0) return -1;
	return 0;
}

static int getS(P a, P b, P c)
{
	return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y);
}
static int getS(P a, P b)
{
	return (a.x - b.x) * (a.y + b.y);
}

static int dist(P a, P b)
{
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}



static bool crsSS(P p1, P p2, P q1, P q2)
{
	if (max(p1.x, p2.x) + EPS < min(q1.x, q2.x)) return false;
	if (max(q1.x, q2.x) + EPS < min(p1.x, p2.x)) return false;
	if (max(p1.y, p2.y) + EPS < min(q1.y, q2.y)) return false;
	if (max(q1.y, q2.y) + EPS < min(p1.y, p2.y)) return false;
	return sig(p2.sub(p1).det(q1.sub(p1))) * sig(p2.sub(p1).det(q2.sub(p1))) < EPS
		&& sig(q2.sub(q1).det(p1.sub(q1))) * sig(q2.sub(q1).det(p2.sub(q1))) < EPS;
}

int main() {
	int N = 5;
	vector<int> x(N), y(N);
	vector<P> p(5);
	for (int i = 0; i < N; i++)
	{
		cin >> x[i] >> y[i];
		p[i] = P(x[i], y[i]); 
	}
	vector<int> ar({ 0, 1, 2, 3, 4 });
	do{
		bool flag = true;
		for (int ii = 0; ii < N; ii++)
		{
			int i = ar[(ii)];
			int j = ar[(ii + 2) % 5];
			int k = ar[(ii + 3) % 5];
			int l = ar[(ii + 1) % 5];
			if (getS(x[i], y[i], x[j], y[j], x[k], y[k]) <= 0){
				flag = false;
			}
			if (!crsSS(p[i], p[l], p[j], p[k])) flag = false;
		}
		if (flag) {
			cout << "YES" << endl;
			return 0;
		}
	} while (next_permutation(ar.begin(), ar.end()));
	cout << "NO" << endl;
}
0