KMCv2 014

KMC

成績

  1. A……AC/0WA 0:21
  2. B……-/-
  3. C……-/1WA

Aを手早く通せたので3/6位

A

立方体を回転させたときに見える面とかを頑張って調べて実装するだけ。

B

しらん

C

点を座標でソートする。

点iと、points[i+1..N] 内の点からあと K-1 個選んで最小の凸多角形を求めるっていうのを全ての i についてやって、そのうち一番面積が小さかったやつを答にする。

最小の凸多角形を求めるには points[i+1..N] 内の点を点iからの角度でソートして、

dp[a][b][k] := 最後に点b, その前に点aを通るような頂点数kの凸多角形のうち最小のものの面積

としてDPする。