斜率小于0的连线数量-归并排序
题目：二维平面上N个点之间共有C(n,2)条连线。求这C(n,2)条线中斜率小于0的线的数量。二维平面上的一个点，根据对应的X Y坐标可以表示为(X,Y)。例如：(2,3) (3,4) (1,5) (4,6)，其中(1,5)同(2,3)(3,4)的连线斜率 < 0，因此斜率小于0的连线数量为2。第1行：1个数N，N为点的数量(0 <= N <= 50000)第2 - N + 1行：N个点的坐标，坐标为整数。(0 <= X[i], Y[i] <= 10^9)输出斜率小于0的连线的数量。(2,3) (2,4)以及(2,3) (3,3)这2种情况不统计在内。
#include<iostream>#include <algorithm>#include <vector>using namespace std;const int MAXN = 50002;typedef struct POINT{int x,y;}Point;Point point[MAXN];int N;__int64 sum;bool cmp(const Point &a, const Point &b){if (a.x == b.x){return a.y < b.y;}return a.x < b.x;}void Merge(vector<int>&Y,int l, int mid, int r){vector<int>L;vector<int>R;for (int i = l; i <= mid; ++ i){L.push_back(Y[i]);}for (int i = mid + 1; i <= r; ++ i){R.push_back(Y[i]);}int p = 0,q = 0,k = l;while (p < L.size() && q < R.size()){if (L[p] <= R[q]){Y[k++] = L[p++];}else{sum += L.size() - p;//mid - l - p + 1;Y[k++] = R[q++];}}while (p<L.size()){Y[k++] = L[p++];}while (q<R.size()){Y[k++] = R[q++];}}void MergeSort(vector<int> &Y,int l, int r){if (l < r){int mid = (l+r)>>1;MergeSort(Y,l,mid);MergeSort(Y,mid+1,r);Merge(Y,l,mid,r);}}int main(){while (cin >> N){sum = 0;for (int i = 0; i < N; ++ i){cin >> point[i].x >> point[i].y;}sort(point,point+N,cmp);vector<int>Y;for (int i = 0; i < N; ++ i){Y.push_back(point[i].y);}MergeSort(Y,0,N-1);cout << sum << endl;}return 0;}