给定平面内若干个点，统计其中的顺序对个数。对于任意两个点p0(x0, y0) p1(x1, y1)，若x0 < x1且y0 < y1，则称p0与p1为顺序对。
我自己试了一些例子，答案也都是对的。
具体代码如下
#include<iostream>
#include<vector>
using namespace std;
#define NL 50000
long long int ans;
struct point{
double x,y;
}p[NL],s[NL];
static void mergex(point data[], int first, int mid, int last, point sorted[]){
int i = first, j = mid;
int k = 0;
while (i < mid && j < last)
if (data[i].x < data[j].x){
sorted[k].x =data[i].x;
sorted[k++].y =data[i++].y;}
else{
sorted[k].x =data[j].x;
sorted[k++].y =data[j++].y;}
while (i < mid){
sorted[k].x =data[i].x;
sorted[k++].y =data[i++].y;}
while (j < last){
sorted[k].x =data[j].x;
sorted[k++].y =data[j++].y;}
for (int v = 0; v < k; v++){
data[first+v].x=sorted[v].x;
data[first+v].y=sorted[v].y;}
}
static void mergeSortx(point data[], int first, int last, point sorted[]){
if (first + 1 < last){
int mid = (first + last) / 2;
mergeSortx(data, first, mid, sorted);
mergeSortx(data, mid, last, sorted);
mergex(data, first, mid, last, sorted);
}
}
static void mergey(point data[], int first, int mid, int last, point sorted[]){
int i = first, j = mid;
int k = 0;
while (i < mid && j < last)
if (data[i].y < data[j].y){
sorted[k].x =data[i].x;
sorted[k++].y =data[i++].y;}
else{
ans +=mid - i;
sorted[k].x =data[j].x;
sorted[k++].y =data[j++].y;}
while (i < mid){
sorted[k].x =data[i].x;
sorted[k++].y =data[i++].y;}
while (j < last){
sorted[k].x =data[j].x;
sorted[k++].y =data[j++].y;}
for (int v = 0; v < k; v++){
data[first+v].x=sorted[v].x;
data[first+v].y=sorted[v].y;}
}
static void mergeSorty(point data[], int first, int last, point sorted[]){
if (first + 1 < last){
int mid = (first + last) / 2;
mergeSorty(data, first, mid, sorted);
mergeSorty(data, mid, last, sorted);
mergey(data, first, mid, last, sorted);
}
}
int main(){
int n;
double a,b;
cin>>n;
if(n>50000||n<0){
return 0;}
for(int i=0;i<n;i++){
cin>>a;
cin>>b;
p[i].x=a;
p[i].y=b;}
mergeSortx(p,0,n,s);
mergeSorty(p,0,n,s);
long long int re=(n*(n-1)/2)-ans;
cout<<re<<endl;
return 0;}
不知道你这个问题是否已经解决, 如果还没有解决的话: