結果

問題 No.199 星を描こう
ユーザー bal4ubal4u
提出日時 2019-06-07 20:51:40
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 1,416 bytes
コンパイル時間 1,135 ms
コンパイル使用メモリ 31,488 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-15 19:25:54
合計ジャッジ時間 1,930 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

// yukicoder: 199 星を描こう
// 2019.6.7 bal4u

#include <stdio.h>

typedef struct { int x, y; } PP;
typedef struct { PP s, e; } SEG, LINE;
PP pp[5];
int a[5], f[5];

PP vsub(PP p1, PP p2) { PP r; r.x = p1.x - p2.x, r.y = p1.y - p2.y; return r; }
int cross(PP a, PP b) { return a.x * b.y - a.y * b.x; }
int dot(PP a, PP b) { return a.x * b.x + a.y * b.y; }
int norm(PP a) { return a.x * a.x + a.y * a.y; }
int ccw(PP p0, PP p1, PP p2) { PP a, b;	int t;
	a = vsub(p1, p0), b = vsub(p2, p0), t = cross(a, b);
	if (t > 0) return 1;	if (t < 0) return -1;
	if (dot(a, b) < 0) return 2; if (norm(a) < norm(b)) return -2;
	return 0;
}
int is_intersectSS(SEG s1, SEG s2) {
	return ccw(s1.s, s1.e, s2.s) * ccw(s1.s, s1.e, s2.e) <= 0 &&
		   ccw(s2.s, s2.e, s1.s) * ccw(s2.s, s2.e, s1.e) <= 0;
}

int rec(int id) {
	int i, k;
	SEG s1, s2;
	if (id == 5) {
		if (ccw(pp[a[0]], pp[a[3]], pp[a[4]]) != 1) return 0;
		if (ccw(pp[a[1]], pp[a[4]], pp[a[0]]) != 1) return 0;
		s1.s = pp[a[0]], s1.e = pp[a[2]], s2.s = pp[a[1]], s2.e = pp[a[3]];
		return is_intersectSS(s1, s2);
	}
	for (i = 1; i < 5; i++) {
		if (f[i]) continue;
		f[i] = 1, a[id] = i, k = 1;
		if (id > 1) k = ccw(pp[a[id]], pp[a[id-2]], pp[a[id-1]]);
		if (k == 1 && rec(id+1)) return 1;
		f[i] = 0;
	}
	return 0;
}

int main()
{
	int i;

	for (i = 0; i < 5; i++) scanf("%d%d", &pp[i].x, &pp[i].y);
	f[0] = 1, a[0] = 0;
	puts(rec(1)? "YES": "NO");
	return 0;
}
0