E - Kite 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 450 点

問題文

あけましておめでとうございます！正月の外遊びといえば凧揚げですね！

1 から N の番号がついた N 人の人が河原で凧揚げをしようとしています。
河原に面する川は直線状に流れているので、以降では川の方向を x 軸、高さ方向を y 軸とする 2 次元座標で考えます。
人 i は地点 (A_i, 0) に立って地点 (B_i, 1) に凧を揚げようとしています。
しかし、人や凧の衝突、および凧糸が絡まることを避けるため、以下の条件を満たす時、人 i と人 j (i \neq j) は同時に凧を揚げることは出来ません。

  • 「(A_i, 0) と (B_i, 1) を結ぶ線分」と「(A_j, 0) と (B_j, 1) を結ぶ線分」が交点を持つ。(線分の端点同士が接する場合も含む。)

以上の制約を守った上で、最大で何人が同時に凧を揚げることが出来ますか？

制約

  • 1 \leq N \leq 2\times 10^5
  • 0 \leq A_i \leq 10^9
  • 0 \leq B_i \leq 10^9
  • 入力される値は全て整数

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

同時に凧を揚げることが出来る人数の最大値を出力せよ。

入力例 1

3
3 5
1 4
2 6

出力例 1

2

人 1 と人 2 、および人 2 と人 3 は同時に凧を揚げることが出来ますが、人 1 と人 3 は同時に凧を揚げることが出来ません。
よって、適切な組み合わせを選べば 2 人が同時に凧を揚げられる一方で、3 人が同時に凧を揚げることは不可能です。よって答えは 2 人です。

入力例 2

5
1 2
1 3
1 4
1 5
1 6

出力例 2

1

入力例 3

10
440423913 766294629
725560240 59187619
965580535 585990756
550925213 623321125
549392044 122410708
21524934 690874816
529970099 244587368
757265587 736247509
576136367 993115118
219853537 21553211

出力例 3

4

Score : 450 points

Problem Statement

Happy New Year! When it comes to outdoor play on New Year's, it's kite flying!

N people numbered 1 to N are trying to fly kites by the riverbank.
The river facing the riverbank flows in a straight line, so from now on, we consider a two-dimensional coordinate system where the x-axis is the direction of the river and the y-axis is the height direction.
Person i is standing at point (A_i, 0) and trying to fly a kite at point (B_i, 1).
However, to avoid collisions of people and kites, and to avoid kite strings getting tangled, persons i and j (i \neq j) cannot fly kites at the same time if the following condition is satisfied:

  • The "line segment connecting (A_i, 0) and (B_i, 1)" and the "line segment connecting (A_j, 0) and (B_j, 1)" have an intersection point. (This includes the case where the endpoints of the line segments touch each other.)

What is the maximum number of people who can fly kites at the same time while respecting the above constraint?

Constraints

  • 1 \leq N \leq 2\times 10^5
  • 0 \leq A_i \leq 10^9
  • 0 \leq B_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Output the maximum number of people who can fly kites at the same time.

Sample Input 1

3
3 5
1 4
2 6

Sample Output 1

2

Persons 1 and 2, as well as persons 2 and 3, can fly kites at the same time, but persons 1 and 3 cannot fly kites at the same time.
Therefore, two people, if chosen appropriately, can fly kites at the same time, while it is impossible for three people to fly kites at the same time. Thus, the answer is 2.

Sample Input 2

5
1 2
1 3
1 4
1 5
1 6

Sample Output 2

1

Sample Input 3

10
440423913 766294629
725560240 59187619
965580535 585990756
550925213 623321125
549392044 122410708
21524934 690874816
529970099 244587368
757265587 736247509
576136367 993115118
219853537 21553211

Sample Output 3

4