灯塔(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
提示
注意机器中整型变量的范围，C/C++中的int类型通常被编译成32位整数，其范围为[-231, 231 – 1]，不一定足够容纳本题的输出。
这道题其实和Openjudge 求排列的逆序数大同小异，那道题和这道题是一样的，都分成两个维度，前面那道题是数组的下标和数组的内容，而这道题则是x,y坐标，都是一样的道理，可是没看出来，后来参考别人的代码才有这种感觉。
贴代码：（这道题没有AC，95分，最后一个点数据范围太大TLE了）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | #include<iostream> #include<cstdlib> using namespace std; struct point{ int x; int y; }; void Merge(int *a,int s,int m,int e,int *b){ int ptr1=s,ptr2=m+1,ptr=s; while (ptr1<=m&&ptr2<=e){ if (a[ptr1]<a[ptr2]) b[ptr++]=a[ptr1++]; else b[ptr++]=a[ptr2++]; } while (ptr1<=m){ b[ptr++]=a[ptr1++]; } while (ptr2<=e){ b[ptr++]=a[ptr2++]; } for(int i=s;i<=e;i++){ a[i]=b[i]; } } long long getN(int *a,int s,int m,int e){ long long re=0; int ptr1=s,ptr2=m+1; while(ptr1<=m&&ptr2<=e){ if(a[ptr1]<a[ptr2]){ re+=e-ptr2+1; ptr1++; }else{ ptr2++; } } return re; } long long MergeSort(int *a,int s,int e,int *b){ if(s<e){ long long total=0; int m=s+(e-s)/2; total+=MergeSort(a,s,m,b); total+=MergeSort(a,m+1,e,b); total+=getN(a,s,m,e); Merge(a,s,m,e,b); return total; } return 0; } int cmp(const void * v1,const void *v2){ return ((point *)v1)->x-((point *)v2)->x; } int main(){ int n; cin>>n; point * arrayp=new point[n]; for(int i=0;i<n;i++){ cin>>arrayp[i].x>>arrayp[i].y; } qsort(arrayp,n,sizeof(point),cmp); int * array=new int[n]; int * array2=new int[n]; for(int i=0;i<n;i++){ array[i]=arrayp[i].y; } long long re=MergeSort(array,0,n-1,array2); cout<<re; delete []arrayp; delete []array; delete []array2; } |