경사 율 0 이하 의 연결선 수량 - 병합 정렬

제목:
2 차원 평면 상 N 개 점 사이 에는 모두 C (n, 2) 개의 연결선 이 있다.이 C (n, 2) 개의 선 중 경사 율 이 0 보다 작은 선의 수량 을 구하 십시오.
2 차원 평면 상의 한 점 은 대응 하 는 X Y 좌표 에 따라 (X, Y) 로 표시 할 수 있다.예 를 들 어 (2, 3) (3, 4) (1, 5) (4, 6), 그 중에서 (1, 5) 와 (2, 3) (3, 4) 의 연결선 기울 임 률 이 0 이 므 로 기울 임 률 이 0 보다 적은 연결선 수량 은 2 이다.
Input

 1 ：1  N，N     (0 <= N <= 50000)
 2 - N + 1 ：N     ，     。(0 <= X[i], Y[i] <= 10^9)

Output

      0      。(2,3) (2,4)  (2,3) (3,3) 2        。

입력 예제

4
2 3
3 4
1 5
4 6

출력 예제

2

제목 분석:
이 문제 의 또 다른 표현 은 경사 율 이 0 보다 많은 수량 을 구 하 는 것 이 고 사실은 본질 이 같다 는 것 이다.
제목 의 데 이 터 량 을 보면 직접 매 거 할 수 없다 는 것 을 알 수 있다.
먼저 우리 가 발견 한 경사 율 이 0 보다 적은 상황 의 직선 은 직각 좌표계 에서 2, 4 상한 을 거 친 직선 이다. 모든 점 이 1 상한 에 있 기 때문에 만약 에 두 점 이 경사 율 이 0 보다 적 으 면 (x1, y1) (x2, y2) 반드시 만족 (x2 > x1, y1 > y2) 또는 반대 (x1 > x2, y2 > y1)사실은 24 상한 직선 상의 점 을 거 쳐 만족 하 는 조건 이다.
그렇다면 그렇다면 우 리 는 먼저 x 를 작은 것 에서 큰 것 으로 정렬 할 수 있다. 그러면 모든 점 에 대해 이 점 과 경사 율 이 0 보다 적은 점 은 바로 뒤의 모든 점 에서 세로 좌표 y 가 현재 점 의 세로 좌표 보다 작은 점 이다. 그러면 직선 의 수량 은 현재 y 값 보다 작은 점 의 개수 이다. 여기까지 판단 하면 일반인 들 은 매 거 를 생각 하고 모든 점 에 대해 직접 뒤의 y 를 구한다.현재 y 값 보다 작은 점 의 개 수 를 구하 고 화 해 를 구하 면 됩 니 다. 그러나 시간 이 초 과 될 수 있 습 니 다.
            역순 수 에 익숙 한 사람 에 게 y 값 이 뒤의 y 값 보다 크 고 사실은 역순 수 라 는 것 을 알 게 될 것 이다. 역순 수 란 무엇 입 니까? 바로 각 수 에 아래 표 시 된 i, j 가 있 습 니 다. i < j 일 때 a [i] > a [j] 가 있다 면 이것 은 역순 수 입 니 다.
          따라서 모든 y 점 을 구하 고 뒤에 그의 점 보다 작은 개수 의 총 화 를 구하 면 사실은 y 좌표 로 구 성 된 서열 의 역순 대 수 를 구 하 는 것 이다.
역순 대수 가 뚜렷 해서 정렬 을 합치 면 바로 해결 된다.
여기 서 세부 사항 을 주의 하 세 요. 그것 은 경사 율 이 존재 하지 않 고 경사 율 이 0 인 상황 을 어떻게 회피 하 는 지 하 는 것 입 니 다. 경사 율 이 0 인 것 은 y 값 과 같 습 니 다. 여기 서 역순 수 를 구 할 때 똑 같은 판단 을 하지 않 으 면 회피 할 수 있 습 니 다. 경사 율 이 존재 하지 않 는 것 은 x 가 같은 것 입 니 다. 어떻게 회피 하 는 것 입 니까? 여 기 는 x 로 정렬 할 때 두 점 의 x 가 같 으 면 그들의 y 는 어 릴 때 부터 큰 순서 로 정렬 합 니 다.샘플 은 x 와 같은 점 에 대해 역순 이 없 을 것 이다. 그러면 당연히 뒤에서 역순 을 구 할 때 도 계산 에 포함 되 지 않 을 것 이다.
코드:

#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;
}