题目描述
给你平面上 N N N 个点，求有多少个点右上方没有其他点（包括正上方和正右方）。
输入格式
一行 N N N，表示点的数量。
接下来 N N N 行，每行两个数 x , y x, y x,y，表示一个点的坐标。
输出格式
一行表示答案。
样例
样例输入1：
4
1 0
0 1
1 1
0 0
样例输出1：
1
数据范围
对于 50 % 50\% 50% 的数据， N ≤ 1000 N \le 1000 N≤1000
对于 100 % 100\% 100% 的数据， N ≤ 100000 N \le 100000 N≤100000， x x x 和 y y y 的绝对值在 int 范围，不会出现两个坐标相同的点。
题解
假设选了 ( x , y ) (x, y) (x,y)，则下一次选的点的坐标要么 x x x 大于当前的 x x x，要么 y y y 大于当前的 y y y 且 x x x 小于当前的 x x x。
将 x x x 坐标从大到小排序，这样只用考虑第 2 2 2 种情况了。
将每个点依次遍历，加入单调栈进行维护 y y y，最后输出单调栈的长度即可。
代码：
stack<int> st;
pair<int, int> a[1000010];
int main(){scanf("%d", &n);for(int i = 1; i <= n; ++ i){scanf("%d %d", &a[i].first, &a[i].second);}//排序sort(a + 1, a + n + 1);//维护单调栈for(int i = 1; i <= n; ++ i){while(!st.empty() && st.top() <= a[i].second){st.pop();}st.push(a[i].second);}printf("%d", st.size());return 0;
}
