各位码农进来看看这个题怎么用java解决

仰望过去 发布于 2013/11/13 16:46
阅读 494
收藏 0

灯塔(LightHouse)
描述
海上有许多灯塔,为过路船只照明。从平面上看,海域范围是[1, 10^7] × [1, 10^7] 。

 

(图一)

如图一所示,每个灯塔都配有一盏探照灯,照亮其东北、西南两个对顶的直角区域。探照灯的功率之大,足以覆盖任何距离。灯塔本身是如此之小,可以假定它们不会彼此遮挡。

 

(图二)

若灯塔A、B均在对方的照亮范围内,则称它们能够照亮彼此。比如在图二的实例中,蓝、红灯塔可照亮彼此,蓝、绿灯塔则不是,红、绿灯塔也不是。

现在,对于任何一组给定的灯塔,请计算出其中有多少对灯塔能够照亮彼此。

输入
共n+1行。

第1行为1个整数n,表示灯塔的总数。

第2到n+1行每行包含2个整数x, y,分别表示各灯塔的横、纵坐标。

输出
1个整数,表示可照亮彼此的灯塔对的数量。

输入样例
3
2 2
4 3
5 1
输出样例
1
限制
1 ≤ n ≤ 2×10^5

灯塔的坐标x, y是整数,且不同灯塔的x, y坐标均互异

1 ≤ x, y ≤ 10^7

加载中
0
fneg
fneg
每个灯塔本身可以看成一个集合,两个灯塔能相互照亮,就说明他们的集合有交集,按照这个思路应该能解出来
0
13123123
13123123
我不是码弄 不会解
0
K__
K__

若A、B彼此照亮则x(A)<x(B)并且y(A)<y(B)

先按x升序排序,再找到y(i)<y(j),即i和j能相互照亮

0
CoserSeu
CoserSeu
求全序关系的坐标对数量。
0
CoserSeu
CoserSeu
为这些坐标维持x,y两个索引,分别对应以x和y从小到大排列的坐标。这两个索引可以从第一个坐标输入时便开始维持,每加入一个坐标,通过二分查找找与其全序的坐标个数。
0
魔神翼
魔神翼
哪个OJ的题么?
返回顶部
顶部