結果

問題 No.199 星を描こう
ユーザー shioyashioya
提出日時 2021-02-07 02:49:06
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,081 bytes
コンパイル時間 1,750 ms
コンパイル使用メモリ 180,508 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-22 10:50:36
合計ジャッジ時間 2,709 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

/*
 * Convex Hull (Graham Scan)
 * O(n log n)
 */

import std;
// utils
alias Tuple!(long, long) Vec2;
Vec2 sub(Vec2 p, Vec2 q){ return Vec2(p[0]-q[0], p[1]-q[1]); }
long det(Vec2 p, Vec2 q){ return p[0]*q[1]-p[1]*q[0]; }

Vec2[] convex_hull(Vec2[] ps){
	int n = ps.length.to!int;
	Vec2[] qs;

	// downward convex
	foreach(i; 0..n){
		while(qs.length>1){
			Vec2 curr = sub(qs[$-1], qs[$-2]);
			Vec2 next = sub(ps[i], qs[$-1]);
			if(det(curr, next)>0) break;
			qs = qs[0..$-1];
		}
		qs ~= ps[i];
	}

	// upward convex
	int t = qs.length.to!int;
	foreach_reverse(i; 0..n-1){

		while(qs.length>t){
			Vec2 curr = sub(qs[$-1], qs[$-2]);
			Vec2 next = sub(ps[i], qs[$-1]);
			if(det(curr, next)>0)break;
			qs = qs[0..$-1];
		}
		qs ~= ps[i];
	}
	return qs;
}

void main(){
	Vec2[] points;
	foreach(i; 0..5){
		auto input = readln.chomp.split;
		points ~= Vec2(input[0].to!long, input[1].to!long);
	}
	points.sort!("a[0]==b[0]?a[1]<b[1] : a[0]<b[0]");
	auto res = convex_hull(points);
	writeln(res.length-1>=5? "YES" : "NO");
}
0