結果

問題 No.199 星を描こう
ユーザー shioyashioya
提出日時 2021-02-07 02:44:45
言語 D
(dmd 2.107.1)
結果
WA  
実行時間 -
コード長 1,098 bytes
コンパイル時間 4,155 ms
コンパイル使用メモリ 234,804 KB
実行使用メモリ 4,508 KB
最終ジャッジ日時 2023-09-04 12:07:31
合計ジャッジ時間 5,745 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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[1]");
	auto res = convex_hull(points);
	res.writeln();
	writeln(res.length-1>=5? "YES" : "NO");
}
0