Time Limit: 2 sec / Memory Limit: 1024 MiB

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 (,0) and trying to fly a kite at point (,1).
However, to avoid collisions of people and kites, and to avoid kite strings getting tangled, persons i and j (i  j) cannot fly kites at the same time if the following condition is satisfied:

• The "line segment connecting (​,0) and (,1)" and the "line segment connecting (,0) and (,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≤N≤
• 0≤​≤
• 0≤≤
• All input values are integers.

---

Input

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

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

---

考察点

1）LIS（最长递增子序列）问题。

LIS问题是算法竞赛中的一个经典问题，要求在一个数组中找出最长严格递增子序列的长度。

核心解法：贪心 + 二分查找。

        （1）创建一个数组 lst 用于存储当前的最优递增序列。

        （2）遍历原数组中的每个元素：

                ①如果当前元素比 lst 中所有元素都大，就将其添加到末尾；

                ②否则，用当前元素替换 lst 中第一个大于等于它的元素。

        （3）最终 lst 的长度就是答案。

注意： lst 中的元素不一定是最优的递增序列，但它维护了正确长度。这是因为我们只关心长度而不关心具体序列，所以可以用贪心策略保证长度正确。

2）问题转化技巧：从几何约束到LIS

原问题的几何意义：

• 每个人对应一条从到的线段

• 两条线段相交

• 可以同时放风筝的条件是两条线段不相交
   A和B同时递增或同时递减

关键转化步骤：

（1）排序技巧：按 A 升序排序，当 A 相同时按 B 降序排序。

        为什么要这样排序？

        当 A 相同时，两个人站在同一个位置，他们的线段必然相交；

        按 B 降序排序可以避免在LIS中选择多个 A 相同的点。

（2）转化为LIS：排序后，我们只需要在 B 序列中找最长严格递增子序列。

        因为如果 A 递增且 B 也递增，那么任意两线段都不相交；

        排序保证了 A 是非递减的，但我们需要严格递增的 B。

---

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
    int a,b;
};
bool cmp(node x,node y){
    if(x.a!=y.a)return x.a<y.a;
    else return x.b>y.b;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    vector<node>v(n);
    for(int i=0;i<n;i++)cin>>v[i].a>>v[i].b;
    sort(v.begin(),v.end(),cmp);
    vector<int>B;
    for(int i=0;i<n;i++)B.push_back(v[i].b);
    vector<int>lis;
    for(int i=0;i<n;i++){
        auto it=lower_bound(lis.begin(),lis.end(),B[i]);
        if(it==lis.end())lis.push_back(B[i]);
        else *it=B[i];
    }
    cout<<lis.size();
    return 0;
}