結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 WA -
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 1 ms
6,940 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 1 ms
6,940 KB
testcase_15 WA -
testcase_16 AC 1 ms
6,940 KB
testcase_17 AC 1 ms
6,940 KB
testcase_18 WA -
testcase_19 AC 1 ms
6,944 KB
testcase_20 AC 1 ms
6,944 KB
testcase_21 AC 1 ms
6,948 KB
testcase_22 AC 1 ms
6,940 KB
testcase_23 AC 1 ms
6,940 KB
testcase_24 AC 1 ms
6,940 KB
testcase_25 WA -
testcase_26 AC 1 ms
6,940 KB
testcase_27 AC 1 ms
6,940 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[1]");
	auto res = convex_hull(points);
	writeln(res.length-1>=5? "YES" : "NO");
}
0