Cod sursa(job #206301)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 5 septembrie 2008 18:58:54
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

const int N_MAX = 50010;

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

int dmin(int v[N_MAX], int l)
{
	int st = 0, dr = l, inc = 1, sf = 1, dstst = 0, dstdr = 0;
	for (int i = 1; i <= N; i ++) {
		if (v[i] < st) dstst += (st - v[i]);
		if (v[i] > dr) dstdr += (v[i] - dr);
	}
	while (v[inc] < st) inc ++;
	while (v[sf] <= dr) sf ++;
	int MIN = dstst + dstdr, sum = dstst + dstdr;

	for (int i = 1; i <= v[N]; i ++) {
		st ++, dr ++;
//		sum = dstst + dstdr;

		while (v[inc] < st) inc ++;
//		printf("inc = %d\n", inc);
		while (v[sf] <= dr && sf <= N) sf ++, sum --;
//		printf("sf = %d\n", sf);
//		printf("sum = %d\n", sum);

		sum += (inc - 1);
		sum -= (N - sf + 1);
//		printf("sum = %d\n", sum);
//		printf("\n");

		if (sum < MIN) MIN = sum;
	}

	return MIN;
}

int main()
{
	freopen("tribute.in", "r", stdin);
#ifndef _SCREEN_
	freopen("tribute.out", "w", stdout);
#endif

	int DX, DY;
	scanf("%d %d %d\n", &N, &DX, &DY);
	for (int i = 1; i <= N; i ++) {
		scanf("%d %d\n", &x[i], &y[i]);
	}
	sort(x + 1, x + N + 1);
	sort(y + 1, y + N + 1);

	printf("%d\n", dmin(x, DX) + dmin(y, DY));

	return 0;
}