//G++ RE C++ AC
#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cmath>

using namespace std;

const int MAX = 10000+100;

int Rand(int p, int r)
{
    srand((unsigned)time(NULL));
    return p + rand()%(r-p+1);
}

void Exchange(int &a, int &b)
{
     int tmp = a;
     a = b;
     b = tmp;
}

int Partition(int a[], int p, int r)
{
    int i, j;
	int x = a[r];
    i = p-1;
    for (j=p; j<r; j++)
    {
        if (a[j] <= x)
        {
            i++;
			if (i != j)
                Exchange(a[i], a[j]);   
        }
    }
    Exchange(a[i+1], a[r]);
    return i+1;
}

int RandPartition(int a[], int p, int r)
{
    int i = Rand(p, r);
    Exchange(a[r], a[i]);
    return Partition(a, p, r);
}

int RandSelect(int a[], int p, int r, int i)
{
    if (p == r)
       return a[p];
    int q = RandPartition(a, p, r);
    int k = q-p+1;
    if (i == k)
       return a[q];
    else
       if (i < k)
           return RandSelect(a, p, q-1, i);
       else
           return RandSelect(a, q+1, r, i-k);
}

void QuickSort(int a[], int p, int r)
{
	if (p < r)
	{
		int q = RandPartition(a, p, r);
		QuickSort(a, p, q-1);
		QuickSort(a, q+1, r);
	}
}

int x[MAX], y[MAX], N;

int main(int argc, char *argv[])
{
    scanf("%d", &N);
    int i, sum=0;
    for (i=0; i<N; i++)
        scanf("%d%d", &x[i], &y[i]);
	QuickSort(x, 0, N-1);
	for (i=0; i<N; i++)
		  x[i] = x[i] - i;

    int kx = RandSelect(x, 0, N-1, (N+1)/2);
    int ky = RandSelect(y, 0, N-1, (N+1)/2);

    for (i=0; i<N; i++)
         sum =  sum + abs(y[i]-ky) + abs(x[i]-kx);
	printf("%d\n", sum);
    return EXIT_SUCCESS;
}

• Re:为神马G++就RE， C++却AC (1924) 200830740525 2011-05-07 01:42:50
  • Re:为神马G++就RE， C++却AC (86) jki14 2011-06-17 22:47:58