Pagini recente » Cod sursa (job #643144) | Cod sursa (job #2443211) | Cod sursa (job #569140) | Cod sursa (job #1591057)
#include <fstream>
#include <algorithm>
using namespace std;
const int MAXN = 50005;
const int INF = 1 << 30;
ifstream in("tribute.in");
ofstream out("tribute.out");
int n,dx,dy;
int x[MAXN],y[MAXN];
int rasp_1,rasp_2;
void citire()
{
in >> n >> dx >> dy;
for (int i = 1;i <= n;++i)
in >> x[i] >> y[i];
}
void calculare(int v[],int &rasp,int dim)
{
sort(v + 1, v + n + 1);
v[n + 1] = INF;
v[0] = -INF;
int poz = 1;
int dst[MAXN] = {0}, ddr[MAXN] = {0};
int cati = 0;
for (int i = v[0];i < MAXN && poz <= n;++i)//parcurgere stanga
{
while(poz <= n && v[poz] < i)
{
++cati;
++poz;
}
dst[i] = dst[i - 1] + cati;
}
poz = n;
cati = 0;
for (int i = v[n];i >= 0 && poz > 0;--i)//parcurgere dreapta
{
while(v[poz] > i)
{
++cati;
--poz;
}
ddr[i] = ddr[i + 1] + cati;
}
rasp = INF;
for (int i = 0;i + dim <= v[n];++i)
{
int nr = dst[i] + ddr[i + dim];
if (nr < rasp)
rasp = nr;
}
}
int main()
{
citire();
calculare(x,rasp_1,dx);
calculare(y,rasp_2,dy);
out << rasp_1 + rasp_2 << '\n';
return 0;
}