Problem
農場主ジョンの牛は異なる地点 (x1,y1)…(xn,yn) にいます) そのフィールド (1≤N≤100,000、すべての xi と yi は 1,000,000 を超えない正の奇数です。FD はフィールドを無限のフェンスで分割したいと考えています北から南までの長さ。方程式 x=a で表されます (a は偶数の整数なので、フェンスが牛の位置を通過しないことが保証されます)。彼はまた、無限の長さのフェンスを構築したいと考えています。東から西へ。これは方程式 y=b で表されます。b は偶数の整数です。これら 2 つのフェンスは (a,b) で交差し、フィールドを 4 つの領域に分割します。
FD は、「バランスがとれた」方法で a と b を選択したいと考えています。すべての地域の牛の頭数、つまり牛が多すぎる地域が存在しないようにするためです。これら 4 つの地域の牛の最大頭数を M とすると、FD は M をできるだけ小さくしたいと考えています。 FD がこの M の最小値を決定できるよう支援してください。
入力フォーマット:
入力の最初の行には 1 つの整数 N が含まれます。次の n 行にはそれぞれ、x 座標と y 座標で示される 1 頭の牛の位置が含まれます。
出力形式:
最適なフェンス配置でPDに到達できるMの最小値を出力してください。
<本体>
|
入る |
出力 |
|
7
73
5 5
7 13
3 1
117
5 3
9 1
|
2 |