描述

海上有许多灯塔，为过路船只照明。从平面上看，海域范围是[1, 10^8] × [1, 10^8] 。

（图一）

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

（图二）

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

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

32 24 35 1

1

 1 # include<stdio.h> 2  3 int quick(int a[],int A[],int b, int c){ 4     int inversion = 0; 5     if (c > b){ 6     int middle = (int)((b + c) / 2); 7     int u = b; int v = c; 8     inversion+=quick(a,A,b,middle); 9     inversion+= quick(a, A, middle + 1, c);10     inversion+= merge(a, A, u, middle, v);11     }12     return inversion;13 }14 15 16 int merge(int  a[],int B[], int b, int m, int c){17         int i = b;  int j = m + 1;  int k = 0; int inversion = 0;18         while (i <= m && j <= c)19         {20             if (a[i] <= a[j])21             {  22                 B[k++] = a[i++];                23                 inversion= inversion +c-j+1;24             }25             else{26                 B[k++] = a[j++];27             }28         }29         while (i <= m)30             B[k++] = a[i++];31         while (j <= c)32             B[k++] = a[j++];33 34         for (i = 0; i < k; i++)35             a[b + i] = B[i];36         return inversion;37     }38     39 void main(){40     int A[18] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; int a[18];41     int Source_inversion = 0; int inversion = 0;42     for (int i = 0; i < 18; i++){43         a[i] = rand() % 20;44     }45     for (int i = 0; i < 18; i++){46         printf("%d ", a[i]);47     }48     49     for (int t = 0; t < 17; t++){50         for (int m = t + 1; m < 18;m++ )51         {52             if (a[m] >= a[t])53                 Source_inversion++;54         }55     }56     57     printf("\nSource method: %d\n", Source_inversion);58     59     60     inversion=quick(a,A,0,17);61     printf("\n\n");62     for (int i = 0; i < 18; i++){63         printf("%d  ", a[i]);64     }65     printf("\nMerge sort count:%d",inversion);66     system("pause");67 }