時間制限 : sec, メモリ制限 : KB
Japanese

G: Human Seperation

問題文

単位円の上に人が $10^6$ 人、等間隔に立っています。 $t = \frac{2\pi}{10^6}$ として、$i$ 番目の人は 座標 $(\cos{(it)}, \sin{(it)})$ に立っています。

これら $10^6$ 人の中で、非常に仲が悪いペアが $N$ 組あります。 具体的には、$i = 1, \ldots, N$ について、人 $a_i$ と人 $b_i$ は仲が悪いです。

単位円の管理人である松崎くんは、壁を建設することによって仲の悪いペアを全て分断することにしました。 建設する壁は厚さがなく、とてつもなく長いため、直線と同一視することができます。また、壁同士は交わっても構いません。 ただし、人が立っている場所に壁を建設することは出来ません。 壁を建設するにはコストがかかるので、なるべく少ない数の壁で全てのペアを分断したいです。 目的を達成するためには、いくつの壁を建設する必要があるか求めてください。

定式的に問題を言い換えると以下のようになります:

  • 2次元平面上に単位円があり、円周上の2点からなるペアが $N$ 組与えられます。
  • あなたは平面上に任意に直線を置くことができます。
  • ただし、どの与えられた点も直線上に存在してはいけません。
  • 全てのペアが、いずれかの直線によって分離されるには、直線を最小で何本置く必要があるか求めてください。

「2点が直線によって分離されている」とは、2点をどのような曲線で結んでも、曲線が直線と交わる状態を指します。

制約

  • 入力は全て整数
  • $1 \leq N \leq 2 \times 10^5$
  • $0 \leq a_i < b_i < 10^6$

入力

入力は以下の形式で標準入力から与えられます。

$N$
$a_1$ $b_1$
$:$
$a_N$ $b_N$

出力

答えを1行に出力してください。

入出力例

入力例1

1
0 500000

出力例1

1

円周上の点 $(1, 0)$ と点 $(-1, 0)$ がペアとして与えられます。 ペアは1組しかないので、明らかに1本の直線によって条件を満たすことができます。

入力例2

2
0 333333
333333 666666

出力例2

1

入力例3

5
0 6
1 2
1 8
3 5
4 10

出力例3

2