MOOC数据结构（上）（自主模式）-灯塔(LightHouse)

灯塔(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]，不一定足够容纳本题的输出。

C++：

95分答案：

/*@Date    : 2018-02-05 15:02:45@Author  : 酸饺子 (changzheng300@foxmail.com)@Link    : https://github.com/SourDumplings@Version : $Id$
*//*
https://dsa.cs.tsinghua.edu.cn/oj/problem.shtml?id=1144
解答：
对于n对灯塔， 先把灯塔们按x坐标排序，然后观察y坐标中有多少逆序对*/#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>using namespace std;const int maxn = 4000001;const int SZ = 1<<20;  //快速io
struct fastio{char inbuf[SZ];char outbuf[SZ];fastio(){setvbuf(stdin,inbuf,_IOFBF,SZ);setvbuf(stdout,outbuf,_IOFBF,SZ);}
}io;struct LightHouse
{int x, y;
} data[maxn];int cmpx(const void *a, const void *b)
{return ((LightHouse *)a)->x - ((LightHouse *)b)->x;
}int cmpy(const void *a, const void *b)
{return ((LightHouse *)a)->y - ((LightHouse *)b)->y;
}int binary_search(LightHouse A[], int l, int h, int value)
{while (l < h){int mi = (l + h) >> 1;value < A[mi].y ? h = mi : l = mi + 1;}return --l;
}long long calc_Inv_y(int start, int stop)
{if (stop - start < 2) return 0;int mid = (stop + start) >> 1;// printf("start = %d, stop = %d, mid = %d\n", start, stop, mid);long long cross = 0;LightHouse *temp = new LightHouse[mid-start];for (int i = start, count = 0; i != mid;)temp[count++] = data[i++];qsort(temp, mid-start, sizeof(temp[0]), cmpy);for (int i = mid; i != stop; ++i){int j = binary_search(temp, 0, mid-start, data[i].y) + 1;cross += j;}delete [] temp;long long left = calc_Inv_y(start, mid);long long right = calc_Inv_y(mid, stop);// printf("left = %lld, right = %lld, cross = %lld\n", left, right, cross);return cross + left + right;
}int main(int argc, char const *argv[])
{int n;scanf("%d", &n);int X, Y;for (int i = 0; i != n; ++i){scanf("%d %d", &X, &Y);data[i].x = X;data[i].y = Y;}qsort(data, n, sizeof(data[0]), cmpx);printf("%lld\n", calc_Inv_y(0, n));return 0;
}