結果

問題 No.199 星を描こう
コンテスト
ユーザー bal4u
提出日時 2019-06-07 20:51:40
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 1,416 bytes
コンパイル時間 937 ms
コンパイル使用メモリ 30,592 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-05 22:04:29
合計ジャッジ時間 1,131 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// 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