結果

問題 No.199 星を描こう
コンテスト
ユーザー shioya
提出日時 2021-02-07 02:49:06
言語 D
(dmd 2.109.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

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