結果

問題 No.199 星を描こう
コンテスト
ユーザー ゴリポン先生
提出日時 2026-02-02 10:14:55
言語 D
(dmd 2.111.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,930 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,685 ms
コンパイル使用メモリ 191,280 KB
実行使用メモリ 7,968 KB
最終ジャッジ日時 2026-02-02 10:15:00
合計ジャッジ時間 5,352 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/core/checkedint.d(814): Warning: cannot inline function `core.checkedint.mulu!().mulu`
ulong mulu()(ulong x, uint y, ref bool overflow)
      ^

ソースコード

diff #
raw source code 

module main;
// https://roiti46.hatenablog.com/entry/2015/04/29/yukicoder_No.199_%E6%98%9F%E3%82%92%E6%8F%8F%E3%81%93%E3%81%86 より
// 凸包
import std;

// https://github.com/drken1215/algorithm/blob/master/Geometry/ より
// 2次元ベクトル(整数版)
struct Point {
	long x, y;
	// 加減算
	Point opOpAssign(string op)(Point rhs)
		if (op == "+" || op == "-")
	{
		mixin("x " ~ op ~ "= rhs.x;");
		mixin("y " ~ op ~ "= rhs.y;");
		return this;
	}
	Point opBinary(string op)(Point rhs) const
		if (op == "+" || op == "-")
	{
		mixin("return Point(x " ~ op ~ " rhs.x, y " ~ op ~ " rhs.y);");
	}
	// 比較演算子
	long opCmp(Point rhs) const
	{
		if (x != rhs.x) return x - rhs.x;
		return y - rhs.y;
	}
	// 外積
	long det(Point rhs) const
	{
		return x * rhs.y - y * rhs.x;
	}
	// 内積
	long dot(Point rhs) const
	{
		return x * rhs.x + y * rhs.y;
	}
	// ノルム
	long norm() const
	{
		return dot(this);
	}
}
// グラハムスキャンで凸包を求める(一直線上の3点を含めない)
Point[] convexHull(Point[] P)
{
	const n = P.length.to!int;
	P.sort;
	int k = 0;	// 凸包の頂点数
	auto Q = new Point[](n * 2);	// 構築中の凸包
	// 下側凸包の作成
	foreach (i; 0 .. n) {
		while (k > 1 && (Q[k - 1] - Q[k - 2]).det(P[i] - Q[k - 1]) <= 0) --k;
		Q[k++] = P[i];
	}
	for (int i = n - 2, t = k; i >= 0; i--) {
		while (k > t && (Q[k - 1] - Q[k - 2]).det(P[i] - Q[k - 1]) <= 0) --k;
		Q[k++] = P[i];
	}
	Q.length = k - 1;
	// 最も下にあるものの中で最も左にある頂点を探す
	auto s = Q.minIndex!(
		(Point a, Point b) {
			if (a.y != b.y) return a.y < b.y;
			return a.x < b.x;
		}
	);
	bringToFront(Q[0 .. s], Q[s .. $]);
	return Q;
}

void main()
{
	// 入力
	auto P = new Point[](5);
	foreach (i; 0 .. 5)
		readln.chomp.formattedRead("%d %d", P[i].x, P[i].y);
	// 答えの計算と出力
	if (convexHull(P).length == 5)
		writeln("YES");
	else
		writeln("NO");
}
0