結果

問題 No.199 星を描こう
ユーザー 古寺いろは古寺いろは
提出日時 2015-04-29 00:05:37
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,512 bytes
コンパイル時間 1,415 ms
コンパイル使用メモリ 165,744 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-09 13:43:36
合計ジャッジ時間 1,903 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 1 ms
6,812 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 1 ms
6,944 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 1 ms
6,944 KB
testcase_14 AC 2 ms
6,944 KB
testcase_15 AC 2 ms
6,944 KB
testcase_16 AC 1 ms
6,940 KB
testcase_17 AC 1 ms
6,940 KB
testcase_18 AC 1 ms
6,944 KB
testcase_19 AC 1 ms
6,940 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 1 ms
6,944 KB
testcase_22 AC 2 ms
6,940 KB
testcase_23 AC 1 ms
6,940 KB
testcase_24 AC 2 ms
6,940 KB
testcase_25 AC 2 ms
6,940 KB
testcase_26 AC 1 ms
6,940 KB
testcase_27 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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