#P1828. Monkeys' Pride

    ID: 829 传统题 1000ms 256MiB 尝试: 5 已通过: 1 难度: 10 上传者: 标签>计算几何点定位其他排序Atlas of rruucc@POJ

Monkeys' Pride

描述

背景

山中有许多猴子。每只猴子都希望成为猴王。它们已经为这个问题争论了很多年。现在,你的任务是帮助它们解决这个问题。

问题

猴子们生活在山的不同地方。假设一个点(x,y)(x, y)表示猴子所生活的位置,平面上的每个点表示一个猴子的位置。没有两只猴子生活在同一个点。如果一只猴子住在点(x0,y0)(x_0, y_0),那么它只有在没有其他猴子住在点(x,y)(x, y)且满足xx0x \geq x_0yy0y \geq y_0的条件下,才能成为猴王。例如,山中有三只猴子,分别住在点(2,1)(2, 1)(1,2)(1, 2)(3,3)(3, 3)。只有住在点(3,3)(3, 3)的猴子可以成为猴王。在大多数情况下,可能有很多只猴子可以成为猴王。你的任务是找出所有符合条件的猴子。

输入

输入由多个测试用例组成。每个测试用例的第一行包含一个正整数NN1N500001 \leq N \leq 50000),表示山中猴子的数量。接下来有NN行,每行包含一对整数,表示每只猴子的位置(x,y)(x, y)。两个整数之间用一个空格分隔。每个测试用例以一行00为结束,表示没有更多的测试用例需要处理。

输出

对于每个测试用例,输出一行,表示可以成为猴王的猴子的总数。

输入数据 1

3
2 1
1 2
3 3
3
0 1
1 0
0 0
4
0 0
1 0
0 1
1 1
0

输出数据 1

1
2
1

来源
Atlas of rruucc@POJ