#P1787. 灯塔

灯塔

题目描述

海上有许多灯塔,为过路船只照明。

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

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

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

输入格式

n+1n+1 行。

11 行为 11 个整数 nn,表示灯塔的总数。

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

输出格式

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

3
2 2
4 3
5 1
1

说明

对于 90%90\% 的测例:1n3×1051 ≤ n ≤ 3×10^5

对于 95%95\% 的测例:1n1061 ≤ n ≤ 10^6

全部测例:1n4×1061 ≤ n ≤ 4×10^6

灯塔的坐标 x,yx, y 是整数,且不同灯塔的 x,yx, y 坐标均互异,1x,y1081 ≤ x, y ≤ 10^8

注意本题的输出可能会超出 3232 位整数的范围。