灯塔(LightHouse)

---

Description

As shown in the following figure, If another lighthouse is in gray area, they can beacon each other.

For example, in following figure, (B, R) is a pair of lighthouse which can beacon each other, while (B, G), (R, G) are NOT.

Input

1st line: N

2nd ~ (N + 1)th line: each line is X Y, means a lighthouse is on the point (X, Y).

Output

How many pairs of lighthourses can beacon each other

( For every lighthouses, X coordinates won't be the same , Y coordinates won't be the same )

Example

Input

3 2 2 4 3 5 1

Output

1

Restrictions

For 90% test cases: 1 <= n <= 3 * 105

For 95% test cases: 1 <= n <= 106

For all test cases: 1 <= n <= 4 * 106

For every lighthouses, X coordinates won't be the same , Y coordinates won't be the same.

1 <= x, y <= 10^8

Time: 2 sec

Memory: 256 MB

Hints

The range of int is usually [-231, 231 - 1], it may be too small.

描述

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

（图一）

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

（图二）

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

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

输入

共n+1行。

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

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

输出

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

样例

见英文题面

限制

对于90%的测例：1 ≤ n ≤ 3×105

对于95%的测例：1 ≤ n ≤ 106

全部测例：1 ≤ n ≤ 4×106

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

1 ≤ x, y ≤ 10^8

时间：2 sec

内存：256 MB

这里归并排序只能过掉百分之九十五的样例；

发博客的目的是保存自己的归并模板 具体优化需要用到树状数组 #include<stdio.h> #define maxn 4000005 struct node { long long x,y; }a[maxn]; long long s[maxn],ss[maxn],count; void qsort(node aa[],int l,int r) { if(l<r) { int x=l,y=r; node temp; temp.x=aa[x].x; temp.y=aa[x].y; int t=aa[x].x; while(x<y) { while(x<y && t<aa[y].x) y--; a[x].x=a[y].x; a[x].y=a[y].y; while(x<y && aa[x].x<t) x++; a[y].x=a[x].x; a[y].y=a[x].y; } a[x].x=temp.x; a[x].y=temp.y; qsort(aa,l,x-1); qsort(aa,x+1,r); } } void merge(long long *s,long long *ss,int l,int mid,int r) { int i=l,j=mid+1; int k=l; while(i<=mid && j<=r) { if(s[i]<s[j]) { ss[k++]=s[i++]; count+=r-j+1;//求顺序对 } else ss[k++]=s[j++]; } while(i<=mid) ss[k++]=s[i++]; while(j<=r) ss[k++]=s[j++]; for(i=l;i<=r;i++) s[i]=ss[i]; } void mergesort(long long *s,long long *ss,int l,int r) { int mid=(l+r)/2; if(l<r) { mergesort(s,ss,l,mid); mergesort(s,ss,mid+1,r); merge(s,ss,l,mid,r); } } int main() { int n,i; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%lld%lld",&a[i].x,&a[i].y); qsort(a,1,n); for(i=1;i<=n;i++) s[i]=a[i].y; mergesort(s,ss,1,n); printf("%lld\n",count); }