【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;
}











相关文章
|
11月前
|
算法 搜索推荐
算法分析 | 第一套(渐近分析)
算法分析 | 第一套(渐近分析)
59 0
|
算法 搜索推荐 数据处理
转:如何通过堆排序算法提高文档管理系统的性能
在文档管理系统中,可以通过使用堆排序算法轻松提升性能,尤其是在处理大量文档的排序和查找时。堆排序就像魔法棒一样,能够迅速整理文档,让它们井然有序。堆排序是一种超级高效的排序算法,它的核心思想就是建立一个“最大堆”(或者“最小堆”),然后借助这个特殊的数据结构来排序。通过这种方式,你可以像整理扑克牌一样,轻松地排列文档,让它们按照你的要求排队。
69 0
|
搜索推荐 算法 测试技术
|
存储 算法 搜索推荐
<<算法很美>>——(三)十大排序算法(上)(二)
<<算法很美>>——(三)十大排序算法(上)
<<算法很美>>——(三)十大排序算法(上)(二)
|
算法 搜索推荐 C++
<<算法很美>>——(三)十大排序算法(下)
<<算法很美>>——(三)十大排序算法(下)
<<算法很美>>——(三)十大排序算法(下)
|
算法 搜索推荐 测试技术
<<算法很美>>——(三)十大排序算法(上)(一)
<<算法很美>>——(三)十大排序算法(上)
<<算法很美>>——(三)十大排序算法(上)(一)
|
算法 C++
C++实用技巧:公交换乘算法
C++实用技巧:公交换乘算法
C++实用技巧:公交换乘算法
|
搜索推荐 算法 Java
经典排序算法分析(一)
排序指的是将一组对象按照特定的逻辑顺序重新排列的过程,排序的应用十分广泛,可以说是无处不在,它在商业数据处理和现代科学计算中发挥着举足轻重的作用,目前已知的应用最广泛的排序算法—快速排序,更是被誉为了 20 世纪科学和工程领域的十大算法之一。
120 0
经典排序算法分析(一)