Pagini recente » Cod sursa (job #1132048) | Cod sursa (job #851699) | Cod sursa (job #621519) | Cod sursa (job #1835790) | Cod sursa (job #1591083)
#include <fstream>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
const long long INF = 1ll << 62;
ifstream in("tribute.in");
ofstream out("tribute.out");
int n,dx,dy;
int x[MAXN],y[MAXN];
long long rasp_1,rasp_2;
void citire()
{
in >> n >> dx >> dy;
for (int i = 1;i <= n;++i)
in >> x[i] >> y[i];
}
long long dstx[MAXN], ddrx[MAXN], dsty[MAXN], ddry[MAXN];
void calculare(int v[], long long &rasp,int dim, long long dst[], long long ddr[])
{
sort(v + 1, v + n + 1);
int poz = 1;
//int dst[MAXN] = {0}, ddr[MAXN] = {0};
int cati = 0;
for (int i = v[1];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(poz > 0 && v[poz] > i)
{
++cati;
--poz;
}
ddr[i] = ddr[i + 1] + cati;
}
rasp = INF;
for (int i = 0;i + dim <= v[n];++i)
{
long long nr = dst[i] + ddr[i + dim];
if (nr < rasp)
rasp = nr;
}
}
int main()
{
citire();
calculare(x,rasp_1,dx,dstx,ddrx);
calculare(y,rasp_2,dy,dstx,ddry);
out << rasp_1 + rasp_2 << '\n';
return 0;
}