灯塔（LightHouse）

灯塔（LightHouse）"/>

灯塔（LightHouse）

描述

海上有许多灯塔，为过路船只照明。

（图一）

如图一所示，每个灯塔都配有一盏探照灯，照亮其东北、西南两个对顶的直角区域。探照灯的功率之大，足以覆盖任何距离。灯塔本身是如此之小，可以假定它们不会彼此遮挡。

（图二）

若灯塔A、B均在对方的照亮范围内，则称它们能够照亮彼此。比如在图二的实例中，蓝、红灯塔可照亮彼此，蓝、绿灯塔则不是，红、绿灯塔也不是。

现在，对于任何一组给定的灯塔，请计算出其中有多少对灯塔能够照亮彼此。

输入

共n+1行。

第1行为1个整数n，表示灯塔的总数。

第2到n+1行每行包含2个整数x, y，分别表示各灯塔的横、纵坐标。

输出

1个整数，表示可照亮彼此的灯塔对的数量。

样例

输入

3
2 2
4 3
5 1

输出

1

限制

对于90%的测例：

对于95%的测例：

全部测例：

灯塔的坐标x, y是整数，且不同灯塔的x, y坐标均互异

时间：2 sec

内存：256 MB

提示

注意机器中整型变量的范围，C/C++中的int类型通常被编译成32位整数，其范围为，不一定足够容纳本题的输出。

算法思路

根据题意，对于灯塔对，只需且，或者且即可

解法一：暴力解法

struct Point
{int x = 0;int y = 0;
};Point* points = new Point[4000001];bool isGroup(Point& a, Point& b)
{return (a.x > b.x && a.y > b.y || a.x < b.x && a.y < b.y);
}int main()
{int n = 0;scanf("%d\n", &n);for (int i = 0; i < n; ++i){scanf("%d\n", &points[i].x);scanf("%d\n", &points[i].y);}int rel = 0;for (int i = 0; i < n - 1; ++i){for (int j = i + 1; j < n; ++j){if (isGroup(points[i], points[j]))rel++;}}printf("%d\n", rel);
}

解法二：

先将各个灯塔根据x坐标排序，然后取出y坐标，对y坐标进行归并排序的同时，计数“顺序对”，将B数组（下标为j，lo~mi）与C数组（下标为k，mi~hi）归并时，当B[j] < C[k]，B[j]也必小于C[k + mi]~C[hi]，构成(hi - mi - k)个顺序对

#include <cstdio>struct Point
{int x = 0;int y = 0;
};
bool isGroup(Point& a, Point& b);
void merge(Point* points, int lo, int mi, int hi); 
void mergeSort(Point* points, int lo, int hi);
long long invInside(int* pointYs, int lo, int hi);
long long invBetween(int* pointYs, int lo, int mi, int hi);Point* points = new Point[4000001];
Point* B = new Point[4000001];
int*  pointYs = new int[4000001];
int* BY = new int[4000001];int main()
{
#ifndef _OJ_freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#endif//setvbuf(stdin, new char[1 << 20], _IOFBF, 1 << 20);int n = 0;scanf("%d\n", &n);for (int i = 0; i < n; ++i){scanf("%d\n", &points[i].x);scanf("%d\n", &points[i].y);}mergeSort(points, 0, n);for (int i = 0; i < n; ++i)pointYs[i] = points[i].y;long long rel = invInside(pointYs, 0, n);printf("%lld\n", rel);#ifndef _OJ_fclose(stdin);fclose(stdout);
#endifreturn 0;
}bool isGroup(Point& a, Point& b)
{return (a.x > b.x && a.y > b.y || a.x < b.x && a.y < b.y);
}void merge(Point* points, int lo, int mi, int hi)
{Point* A = points + lo;int lb = mi - lo; // Point* B = new Point[lb];for (size_t i = 0; i < lb; B[i] = A[i++]);int lc = hi - mi; Point* C = points + mi;for (int i = 0, j = 0, k = 0; j < lb; ){if (lc <= k || B[j].x < C[k].x) A[i++] = B[j++];if (k < lc && C[k].x <= B[j].x) A[i++] = C[k++];}//delete[] B;
}void mergeSort(Point* points, int lo, int hi)
{if(hi - lo < 2) return;int mi = (hi + lo) >> 1;mergeSort(points, lo, mi);mergeSort(points, mi, hi);merge(points, lo, mi, hi);
}long long invInside(int* pointYs, int lo, int hi)
{long long rel = 0;if (hi - lo < 2) return 0;const int mi = (lo + hi) >> 1;rel += invInside(pointYs, lo, mi);rel += invInside(pointYs, mi, hi);rel += invBetween(pointYs, lo, mi, hi);return rel;
}
long long invBetween(int* pointYs, int lo, int mi, int hi)
{int* A = pointYs + lo;int lb = mi - lo; // int* B = new int[lb];for (size_t i = 0; i < lb; BY[i] = A[i++]);int lc = hi - mi; int* C = pointYs + mi;long long num = 0;for (size_t i= 0, j = 0, k = 0; j < lb;){if (lc <= k || (BY[j] <= C[k])){A[i++] = BY[j++];if (k < lc)num += lc - k;}if ((k < lc) && C[k] <= BY[j])A[i++] = C[k++];}//delete[] B;return num;
}

不预先定义归并排序Point数组B，与Y坐标数组归并排序的数组B，会超时