燈塔(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

32 24 35 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.
描述
海上有許多燈塔，為過路船只照明。
（圖一）
如圖一所示，每個燈塔都配有一盞探照燈，照亮其東北、西南兩個對頂?shù)闹苯菂^(qū)域。探照燈的功率之大，足以覆蓋任何距離。燈塔本身是如此之小，可以假定它們不會彼此遮擋。
（圖二）
若燈塔A、B均在對方的照亮范圍內(nèi)，則稱它們能夠照亮彼此。比如在圖二的實例中，藍、紅燈塔可照亮彼此，藍、綠燈塔則不是，紅、綠燈塔也不是。
現(xiàn)在，對于任何一組給定的燈塔，請計算出其中有多少對燈塔能夠照亮彼此。
輸入
共n+1行。
第1行為1個整數(shù)n，表示燈塔的總數(shù)。
第2到n+1行每行包含2個整數(shù)x, y，分別表示各燈塔的橫、縱坐標。
輸出
1個整數(shù)，表示可照亮彼此的燈塔對的數(shù)量。
樣例
見英文題面
限制
對于90%的測例：1 ≤ n ≤ 3×105
對于95%的測例：1 ≤ n ≤ 106
全部測例：1 ≤ n ≤ 4×106
燈塔的坐標x, y是整數(shù)，且不同燈塔的x, y坐標均互異
1 ≤ x, y ≤ 10^8
時間：2 sec
內(nèi)存：256 MB
這里歸并排序只能過掉百分之九十五的樣例；
發(fā)博客的目的是保存自己的歸并模板具體優(yōu)化需要用到樹狀數(shù)組
#include<stdio.h>#define maxn 4000005struct 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;//求順序?qū)?	}		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);}