547
技術社區[雲棲]
【Tsinghua】歸並排序：燈塔(LightHouse)
之前在清華的OJ上做過一些好題，但是因為擔心版權問題，一直沒有粘貼出來，今天一舉貼出。
因為題目過去的太久遠，都忘記大概是什麼類型的題目了，能記多少就寫多少了。。。。。哈哈
燈塔(LightHouse)
描述
海上有許多燈塔，為過路船隻照明。從平麵上看，海域範圍是[1, 10^7] × [1, 10^7] 。
（圖一）
如圖一所示，每個燈塔都配有一盞探照燈，照亮其東北、西南兩個對頂的直角區域。探照燈的功率之大，足以覆蓋任何距離。燈塔本身是如此之小，可以假定它們不會彼此遮擋。
（圖二）
若燈塔A、B均在對方的照亮範圍內，則稱它們能夠照亮彼此。比如在圖二的實例中，藍、紅燈塔可照亮彼此，藍、綠燈塔則不是，紅、綠燈塔也不是。
現在，對於任何一組給定的燈塔，請計算出其中有多少對燈塔能夠照亮彼此。
輸入
共n+1行。
第1行為1個整數n，表示燈塔的總數。
第2到n+1行每行包含2個整數x, y，分別表示各燈塔的橫、縱坐標。
輸出
1個整數，表示可照亮彼此的燈塔對的數量。
輸入樣例
3
2 2
4 3
5 1
輸出樣例
1
限製
對於90%的測例：1 ≤ n ≤ 3×105
對於95%的測例：1 ≤ n ≤ 106
全部測例：1 ≤ n ≤ 4×106
燈塔的坐標x, y是整數，且不同燈塔的x, y坐標均互異
1 ≤ x, y ≤ 10^7
提醒
注意機器中整型變量的範圍，C/C++中的int類型通常被編譯成32位整數，其範圍為[-231, 231 - 1]，不一定足夠容納本題的輸出。
時間：2s，內存：256MB
AC的代碼：
#include <stdio.h>
#include <stdlib.h>
#define MAXN 200002
typedef struct P
{
long x;
long y;
}Point;
Point p[MAXN];
long A[MAXN];
long cunt=0;
long L[MAXN],R[MAXN];
const long M=999999999;
//按照 x 的值從小到大將結構體排序
int cmp(const void *a,const void *b)
{
return (*(Point*)a).x > (*(Point*)b).x ? 1 : -1;
}
void Merge(long Left,long Middle,long Right)
{
long n1=Middle-Left+1;
long n2=Right-Middle;
long i,k;
for(i=1;i<=n1;i++)
L[i]=A[Left+i-1];
for(i=1;i<=n2;i++)
R[i]=A[Middle+i];
L[n1+1]=M;
R[n2+1]=M;
i=1;
long j=1;
for(k=Left;k<=Right;k++)
{
if(L[i]<=R[j])
A[k]=L[i++];
else
{
A[k]=R[j++];
cunt+=n1-i+1; //cunt為全局變量
}
}
}
void Merge_sort(long Left,long Right)
{
long Middle;
if(Left<Right)
{
Middle=(Left+Right)/2;
Merge_sort(Left,Middle); // 二分分解左部分
Merge_sort(Middle+1,Right); // 二分分解有部分
Merge(Left,Middle,Right); //合並兩部分
}
}
int main()
{
long n;
scanf("%d",&n);
long i;
for(i=0;i<n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
//按照 x 坐標進行排序
qsort(p,n,sizeof(p[0]),cmp);
for(i=0;i<n;i++)
A[i+1]=p[i].y;
Merge_sort(1,n);
long tmp=(n*(n-1))>>1;
printf("%ld\n",tmp-cunt);
return 0;
}
最後更新：2017-04-03 05:39:40