本文主要是介绍Tsinghua OJ:灯塔(手排+归并排序),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
灯塔(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;//求顺序对}elsess[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);
}
这篇关于Tsinghua OJ:灯塔(手排+归并排序)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!