清华数据结构PA03 灯塔(LightHouse)

这一题应该也能算是学完邓公的数据结构第二章(vector)的assignment，下面贴出题目的text：

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

（图一）

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

（图二）

若灯塔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^8

时间：2 sec

内存：256 MB

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

       初看这道题，会觉得这就是求一个相对方位的：如果把当前那个灯塔的坐标视作为二维直角坐标系的坐标原点，则我们的目的就是去统计所有其它的灯塔里落在第一和第三象限的灯塔个数。然后对每个灯塔都如此做统计，把落在一三象限的所有灯塔数加总，得出的就是所有能互相照亮的灯塔的数量了。

       用算法描述就是外循环遍历所有灯塔，内循环遍历当前灯塔之后的剩下的所有灯塔，然后两两之间计算方位。至于方位计算的实现，既可以考虑用除法算斜率，也可以考虑使用乘法来实现，如下图所示：

       这一算法的直观性毋庸置疑，因为要考察二维平面点和点之间的方位问题，很容易想到引入坐标系，利用平面解析几何相关的知识去解决。但很遗憾，这样一个双重循环遍历，需要枚举出从n个点里取出2个不同点的所有的排列，它的时间复杂度是 O( C n 2 C_n^2 Cn2​)=O(n²) 。稍微关注一下本题“限制”中的数据量，就能发现，这样一个算法对于本题的数据，能有一半不TLE已经是谢天谢地了。事实上，我自己一开始就是用这样的方法，位置计算用乘法实现，提交代码后从第10个测试样例开始TLE。。。最后只有45分。。。

       至此，我们发现这道题不好用这样一个枚举排列加两两比较的思路去解决（除非决心拿45分打满暴力就跑路2333），这启示我们，应该对点和点之间方位的计算做除了挨个遍历，用解析几何的方法以外的思路去做思考。我们再回头看，点和点之间的方位除了用解析几何的方法去度量，还有什么别的角度可以去刻画这一过程呢？不难发现，一个点要想被另一个点“照亮”，要么这个点在另一个点的右上方，即该点坐标的x，y分量都大于另一个点的x，y分量；要么这个点在另一个点的左下方，即该点坐标的x，y分量都小于另一个点的x，y分量（事实上，从这道题的“限制”栏里可以知道，此处的大于和小于都是严格的）。也就是说，我们只要知道每个点的坐标本身，无需通过别的什么几何方法来做进一步的计算来确定相对方位，只需要知道各个点的坐标分量间的相对次序就行。

       如上图所示，对于点A而言，只有点C在两个分量上的排序都严格大于点A的两个分量，因此点A和点C能相互照亮；而对点B而言，点C能满足“照亮的”要求。

       我们发现，之所以点B和点A不能相互照亮，是因为在x轴上，点B要“大于”点A（排序标准为分量升序排序），而在y轴上，如果按照“照亮”的要求，点B理应也要“大于”点A，但是不幸的是，此时点B却“小于”了点A。于是我们发现，点B和点A在y轴上关于x轴的次序形成了一对逆序对。

       上段话中的最后一句看似有点绕，但实际上已经指示了我们从向量排序以及统计逆序对个数的角度来重新思考这道题里关于位置的量化关系。如果我们把这一观察到的现象不用绕来绕去的文字，而是直观的数学语言来表达出来，便是：

       注意到，对于一组规模为n的点，我们只要统计当前点之后所有的点里，位于右上/左下（单侧）的点的总数即可，因为对于一对能互相照亮的灯塔AB里，说A在B的右上方和说B在A的左下方是等价的。换到n组点里，我们既可以对像A这样的点求所有在它右上方的，也可以对像B这样的点求所有在它的左下方的，两种形式都可以。

       所以事到如今，所有的问题都可以归结到，如何求逆序对这一问题上：用组合数公式算出总的组合数，再减去逆序对，算出来的就是顺序对（“即互相照亮的对数”）。要求逆序对，最简单的方法是利用归并排序来求一维逆序对的情形。因为归并排序会把数组天然地划分为前后两个部分，然后在这两个部分中选取大小合适的元素来依次插入、归并为新的有序数组，故在归并排序中实现求逆序对是比较简单的。只需在原有归并排序的基础上加入一行代码即可。代码如下：

//二路归并排序算法，同时实现求逆序对
void merge(int* _array, int _low, int _high, int& _count)
{	//归并算法，变量_count记录逆序对的个数
    //对分掉_array，划成两个子区间
    int mid = _low + _high >> 1,
        length_of_left = mid - _low,
        length_of_right = _high - mid;
    int* left_part = _array + _low,
       * right_part = _array + mid;
    int left_part_temp[length_of_left];
    for (int i = 0; i < length_of_left; i++)
    {
        left_part_temp[i] = left_part[i];
    }
    //归并
    int i = 0, j = 0, k = 0;
    while (i < length_of_left)
    {
        if (j >= length_of_right || left_part_temp[i] <= right_part[j])
        {
            left_part[k++] = left_part_temp[i++];
        }
        else
        {
            left_part[k++] = right_part[j++];
            //下一行代码为求逆序对个数，若只需实现排序，可以把这行代码去掉同时传入参数里去掉_count
            _count += length_of_left - i;    //与左侧尚未就绪的所有点构成逆序对
        }   
    }
}
void mergeSort(int* _array, int _low, int _high, int& _count)
{	//归并排序算法，变量_count记录逆序对的个数
    if (_high - _low <= 1)  return;
    int mid = _low + _high >> 1;
    mergeSort(_array, _low, mid, _count);
    mergeSort(_array, mid, _high, _count);
    merge(_array, _low, _high, _count);
}

       除了用归并排序求逆序对，还有用线段树、树状数组的方法求逆序对的个数，但本蒟蒻目前还不会，所以直接跳过（逃

       在此基础上，剩下的就很简单了。针对本题中的二维逆序对情形，先对n组点的其中一个分量进行排序，如先对x进行排序，此时n组点已经严格按照x的大小排好先后顺序了——x值大者位于序列的后段。再把这n组点关于分量y的值进行排序，同时统计逆序对的个数。原理就是先前对n组点关于x排序的时候，实际上就已经指定

“ 坐标点( i i i) < < <坐标点( j j j)，当且仅当：座标点( i i i) . x .x .x < < <座标点( j j j) . x .x .x ”

这一次序了，如果在之后的关于y分量的排序时出现了逆序对，说明在“座标点( i i i) . x .x .x < < <座标点( j j j) . x .x .x”的条件下，有“座标点( i i i) . y .y .y > > >座标点( j j j) . y .y .y”，即这两个点彼此处于“左上——右下”的关系。不难看出，以上基于归并排序的统计逆序对的算法的复杂度是 O(nlogn) 的，在数据量较大的时候也能有还不错的效率。

       从这个思路出发，贴出这道题的AC代码，注意和逆序对计数相关的变量要设成double类型，int会导致数据溢出然后WA的：

#include <cstdio>
#include <cctype>
//描述二维平面坐标对的数据结构
typedef struct Coordinate
{
    int x,y;
} coordinate;
coordinate* input = nullptr;
//二路归并排序，顺带实现求逆序对
//归并排序算法
void merge(coordinate* _array, int _low, int _high, double& _count, char _sort_flag)
{   //对分掉_array，划成两个子区间
    int mid = _low + _high >> 1,
        length_of_left = mid - _low,
        length_of_right = _high - mid;
    coordinate* left_part = _array + _low,
              * right_part = _array + mid,
              * left_part_temp = new coordinate[length_of_left];
    for (int i = 0; i < length_of_left; i++)
    {
        left_part_temp[i] = left_part[i];
    }
    //进行归并
    int i = 0, j = 0, k = 0;
    //对x轴直接排序
    if (_sort_flag == 'x')
    {
        while (i < length_of_left)
        {
            if (j >= length_of_right || left_part_temp[i].x <= right_part[j].x)
            {
                left_part[k++] = left_part_temp[i++];
            }
            else
            {
                left_part[k++] = right_part[j++];
            }   
        }
    }
    //对y轴排序的同时求逆序对
    if (_sort_flag == 'y')
    {
        while (i < length_of_left)
        {
            if (j >= length_of_right || left_part_temp[i].y <= right_part[j].y)
            {
                left_part[k++] = left_part_temp[i++];
            }
            else
            {
                left_part[k++] = right_part[j++];
                _count += length_of_left - i;    //与左侧尚未就绪的所有点构成逆序对
            }      
        }
    }
    delete[] left_part_temp;
}
//二路归并排序算法
void mergeSort(coordinate* _array, int _low, int _high, double& _count, char _sort_flag)
{
    if (_high - _low <= 1)  return;
    int mid = _low + _high >> 1;
    mergeSort(_array, _low, mid, _count, _sort_flag);
    mergeSort(_array, mid, _high, _count, _sort_flag);
    merge(_array, _low, _high, _count, _sort_flag);
}
//读入优化，缓冲区数字按位读入，拼接成最终的输出input
template <typename T>
inline T read()
{
    T input = 0;    short sign = 1;    char ch = 0;
    while (! isdigit(ch))
    {
        if (ch == '-')  sign = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        input = (input << 3) + (input << 1) + (ch - '0');
        ch = getchar();
    }
    return sign * input;
}
//主函数
int main()
{
    int size_of_input = read<int>();
    input = new coordinate[size_of_input];
    for (int i = 0; i < size_of_input; i++)
    {
        input[i].x = read<int>();
        input[i].y = read<int>();
    }
    //算法部分，分别对输入坐标数组的x分量和y分量进行排序，并求逆序对
    double count_of_disordered_pairs = 0;
    mergeSort(input, 0, size_of_input, count_of_disordered_pairs, 'x');
    mergeSort(input, 0, size_of_input, count_of_disordered_pairs, 'y');
    double count_of_lighted_pairs = 
    static_cast<double>(size_of_input) * static_cast<double>(size_of_input - 1) / 2 - 
    count_of_disordered_pairs;
    //输出部分
    printf("%.0lf", count_of_lighted_pairs);
    delete[] input;
    return 0;
}

       btw，这道题我写的时候用了优化过的读入方法，因为用getchar按位读取输入再乘起来比直接用scanf读取还要快（什么，你问我为啥不用cin？cin慢的要死，和弟弟一样好嘛，就算关了流同步我还是各种不舒服斯基）。有兴趣的可以移步c++读入优化 - Peper进行进一步阅读。亲测用优化过的读入方法比用scanf在worst case下的速度要快400ms左右，像下面贴出的这样：

       另外再多逼逼几句，这道题a掉之后，再回头看，实际上会发现这道题的本质就是在于如何去定义一个二维点集内元素之间的相互次序的一个问题。就本题而言，它是把次序规定为 :
A ( x i , y i ) < B ( x j , y j )    ⟺    x i < x j a n d y i < y j A(x_i,y_i)<B(x_j,y_j) \iff x_i<x_j \quad and \quad y_i<y_j A(xi​,yi​)<B(xj​,yj​)⟺xi​<xj​andyi​<yj​
有了这样的一个次序以后，就可以围绕这个次序来考察一系列相关的性质balabala的。事实上，还有别的不同的次序定义的方式，而这一类和二维点集元素的次序有关的问题统称为二维偏序问题。有兴趣的可以自行百度或者google 2333（逃