← 返回题目列表

AtCoder · joisc2008_ruins

ruins. 最古老的废墟2(废墟)

中文机器翻译题面 查看原题

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

最古の遺跡2 (Ruins) - 原题 PDF 第 1 页
原题PDF第1页
可复制的 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