以下是来自日本的官方新闻原版PDF,已经完整保存和染色。

可复制的 PDF 提取文本
Ruins: 最古の遺跡2
input ファイル“ruins.in”
output 標準出力
ソースファイルruins.c/ruins.cpp
時間制限1.5 秒/ データ
昔,そこには集落があり,多くの人が暮らしていた.人々は形も大きさも様々な建物を建て
たが,それらの建造物は既に失われている.今では,文献と遺跡から見つかった柱だけが建造
物の位置を知る手がかりである.
文献には神殿の記述がある.神殿は上から見ると凸多角形になっており,その各頂点のとこ
ろに柱があった.(凸多角形とは,全ての内角が180 °未満の多角形のことである.)神殿の内部
に柱があったかどうかはわからない.考古学者たちは,遺跡から見つかった柱を頂点とする凸
多角形のうち,頂点数が最大のものが神殿に違いないと考えた.
柱の位置の座標が与えられるので,それらの柱でできる凸多角形のうち頂点数が最大のもの
を探し,その頂点数を出力するプログラムを書け.
Input. 入力ファイルruins.in から入力を読み込め.入力の1 行目は柱の数を表す整数N(3 ≦
N ≦128) が書かれている.続くN 行は, おのおのの柱の座標を表す.i + 1 行目(1 ≦i ≦N) に
は,i 番目の柱の座標xi, yi(−1000 ≦xi ≦1000, −1000 ≦yi ≦1000) が書かれており,いずれも
整数である.
ただし,どの柱も異なる座標にあり,どの3 本の柱も同一直線上にない.
Output. 出力は,標準出力に行うこと.柱のうちいくつかを頂点とする凸多角形の頂点数の
最大値を出力せよ.
採点基準採点用データのうち,配点の10%分についてはN ≦10 を満たし,配点の20%分に
ついてはN ≦32 を満たし,配点の50%分についてはN ≦64 を満たす.
例
ruins.in 標準出力
6 5
0 2
3 2
5 3
2 0
4 1
2 4
最古の遺跡2–1/1