結果
問題 | No.199 星を描こう |
ユーザー |
|
提出日時 | 2021-02-07 02:44:45 |
言語 | D (dmd 2.109.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,098 bytes |
コンパイル時間 | 3,640 ms |
コンパイル使用メモリ | 238,196 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-22 10:50:29 |
合計ジャッジ時間 | 4,177 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 25 |
ソースコード
/* * 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"); }