pku1723.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 80 行

#include <stdio.h>
#include <algorithm>
#define size 11000
using namespace std;
int x[size], y[size];
int N;

int ABS(int x)
{
	return x > 0 ? x : -x;
}

int CalcX(int X)
{
	int ans = 0;
	int i;
	for (i = 0; i < N; i++)
	{
		ans += ABS(X + i - x[i]);
	}
	return ans;
}

int CalcY(int Y)
{
	int ans = 0;
	int i;
	for (i = 0; i < N; i++)
	{
		ans += ABS(Y - y[i]);
	}
	return ans;
}

int main()
{
	int sumx, sumy;
	int i;
	int ansx, ansy, minx, miny, tmp;
	while (scanf("%d", &N) != -1)
	{
		sumx = 0;
		sumy = 0;
		for (i = 0; i < N; i++)
		{
			scanf("%d %d", &x[i], &y[i]);
			sumx += x[i];
			sumy += y[i];
		}
		sort(x, x + N);
		sort(y, y + N);
		ansx = sumx / N;
		ansy = sumy / N;
		ansx -= N / 2;

		minx = CalcX(ansx + 5);

		for (i = -100; i < 100; i++)
		{
			tmp = CalcX(ansx + i);
			if (tmp < minx)
			{
				minx = tmp;
			}
		}

		miny = CalcY(ansy + 5);
		for (i = -100; i < 100; i++)
		{
			tmp = CalcY(ansy + i);
			if (tmp < miny)
			{
				miny = tmp;
			}
		}
		printf("%d\n", minx + miny);
	}
	return 0;
}