24148번 - 最古の遺跡 2 (Ruins) 다국어

문제

昔,そこには集落があり,多くの人が暮らしていた.人々は形も大きさも様々な建物を建て たが,それらの建造物は既に失われている.今では,文献と遺跡から見つかった柱だけが建造 物の位置を知る手がかりである.

文献には神殿の記述がある.神殿は上から見ると凸多角形になっており,その各頂点のとこ ろに柱があった.(凸多角形とは,全ての内角が 180 °未満の多角形のことである.)神殿の内部 に柱があったかどうかはわからない.考古学者たちは,遺跡から見つかった柱を頂点とする凸 多角形のうち,頂点数が最大のものが神殿に違いないと考えた.

柱の位置の座標が与えられるので,それらの柱でできる凸多角形のうち頂点数が最大のもの を探し,その頂点数を出力するプログラムを書け.

입력

入力の 1 行目は柱の数を表す整数 N(3 ≤ N ≤ 128) が書かれている.続く N 行は, おのおのの柱の座標を表す.i + 1 行目 (1 ≤ i ≤ N) に は,i 番目の柱の座標 x_i, y_i(−1000 ≤ x_i ≤ 1000, −1000 ≤ y_i ≤ 1000) が書かれており,いずれも 整数である.

ただし,どの柱も異なる座標にあり,どの 3 本の柱も同一直線上にない.

출력

出力は,標準出力に行うこと.柱のうちいくつかを頂点とする凸多角形の頂点数の 最大値を出力せよ.

제한

힌트