/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
二次元平面上の第一象限上に N 個のフの字があります。
i\ (1 \leq i \leq N) 個目のフの字は、(x_i-1,y_i) と (x_i,y_i) を結ぶ線分と (x_i,y_i-1) と (x_i,y_i) を結ぶ線分の 2 つを組み合わせた図形です。
あなたは、N 個のフの字から 0 個以上を選び、削除することができます。
適切に削除するフの字を選んだとき、原点から全体が見えるフの字の個数は最大でいくつになりますか？
ここで、原点からあるフの字（便宜上 i 個目のフの字とする）の全体が見える必要十分条件は、以下の通りです。
- 原点、(x_i-1,y_i)、(x_i,y_i)、(x_i,y_i-1) の 4 点を頂点とする四角形の内部（境界を除く）と他のフの字が共通部分を持たない。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq x_i,y_i \leq 10^9
- (x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
x_1 y_1
x_2 y_2
\hspace{0.45cm}\vdots
x_N y_N
出力
原点から全体が見えるフの字の個数の最大値を出力せよ。
入力例 1
3 1 1 2 1 1 2
出力例 1
2
1 個目のフの字を削除したとき原点からは 2 個目のフの字と 3 個目のフの字の 2 つが見えるようになり、これが最大です。
1 つのフの字も削除しない場合、原点からは 1 個目のフの字のみしか見えません。
入力例 2
10 414598724 87552841 252911401 309688555 623249116 421714323 605059493 227199170 410455266 373748111 861647548 916369023 527772558 682124751 356101507 249887028 292258775 110762985 850583108 796044319
出力例 2
10
すべてのフの字を削除せずに残すのが最善です。
Score : 500 points
Problem Statement
There are N 7's drawn in the first quadrant of a plane.
The i-th 7 is a figure composed of a segment connecting (x_i-1,y_i) and (x_i,y_i), and a segment connecting (x_i,y_i-1) and (x_i,y_i).
You can choose zero or more from the N 7's and delete them.
What is the maximum possible number of 7's that are wholly visible from the origin after the optimal deletion?
Here, the i-th 7 is wholly visible from the origin if and only if:
- the interior (excluding borders) of the quadrilateral whose vertices are the origin, (x_i-1,y_i), (x_i,y_i), (x_i,y_i-1) does not intersect with the other 7's.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq x_i,y_i \leq 10^9
- (x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
x_1 y_1
x_2 y_2
\hspace{0.45cm}\vdots
x_N y_N
Output
Print the maximum possible number of 7's that are wholly visible from the origin.
Sample Input 1
3 1 1 2 1 1 2
Sample Output 1
2
If the first 7 is deleted, the other two 7's ― the second and third ones ― will be wholly visible from the origin, which is optimal.
If no 7's are deleted, only the first 7 is wholly visible from the origin.
Sample Input 2
10 414598724 87552841 252911401 309688555 623249116 421714323 605059493 227199170 410455266 373748111 861647548 916369023 527772558 682124751 356101507 249887028 292258775 110762985 850583108 796044319
Sample Output 2
10
It is best to keep all 7's.