結果

問題 No.199 星を描こう
ユーザー n_knuun_knuu
提出日時 2018-06-12 20:55:08
言語 Nim
(2.0.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,670 bytes
コンパイル時間 1,206 ms
コンパイル使用メモリ 66,792 KB
最終ジャッジ日時 2024-11-14 20:27:29
合計ジャッジ時間 1,802 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
/home/judge/data/code/Main.nim(2, 45) Warning: Use the new 'sugar' module instead; future is deprecated [Deprecated]
/home/judge/data/code/Main.nim(2, 59) Error: cannot open file: queues

ソースコード

diff # 

# import sequtils, strutils, strscans, algorithm, math, future, sets, queues, tables # for yukicoder (0.17.1)
import sequtils, strutils, algorithm, math, future, sets, queues, tables # for AtCoder (0.13.0)
template getLine: string = stdin.readLine
template getInteger: int = getLine.parseInt
template getBiggestInteger: int64 = getLine.parseBiggestInt
template getIntSeq: seq[int] = getLine.split.map(parseInt)
template getBigIntSeq: seq[int64] = getLine.split.map(parseBiggestInt)

type
  Point[T] = object
    x, y: T

proc initPoint[T](x, y: T): Point[T] =
  Point[T](x: x, y: y)

proc `+`[T](a, b: Point[T]): Point[T] =
  initPoint(a.x + b.x, a.y + b.y)

proc `-`[T](a, b: Point[T]): Point[T] =
  initPoint(a.x - b.x, a.y - b.y)

proc det[T](a, b: Point[T]): T =
  a.x * b.y - a.y * b.x

proc convex_hull[T](points: seq[Point[T]]): seq[Point[T]] =
  var sorted_points = points
  sorted_points.sort do (p1, p2: Point[T]) -> int:
    result = cmp(p1.x, p2.x)
    if result == 0:
      result = cmp(p1.y, p2.y)
  var lower_hull = sorted_points.get_bounds
  sorted_points.reverse
  result = sorted_points.get_bounds
  discard lower_hull.pop
  discard result.pop
  for point in lower_hull:
    result.add(point)

proc get_bounds[T](points: var seq[Point[T]]): seq[Point[T]] =
  result = @[points[0], points[1]]
  for point in points[2..^1]:
    while result.len > 1 and (result[^1] - result[^2]).det(point - result[^1]) <= 0:
      discard result.pop
    result.add(point)

when isMainModule:
  var points = newSeq[Point[int]](5)
  for i in 0..<5:
    let tmp = getIntSeq
    points[i] = initPoint(tmp[0], tmp[1])
  echo(if points.convex_hull.len == 5: "YES" else: "NO")
0