Pagini recente » Cod sursa (job #2360491) | Cod sursa (job #2628107) | Cod sursa (job #136881) | Cod sursa (job #2365608) | Cod sursa (job #2294542)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("tribute.in");
ofstream fout("tribute.out");
const int NMax = 50001;
struct {int sd, ds, nr;} X[NMax + 5], Y[NMax + 5];
int N, dx, dy, x, y;///DP[i] este suma minima pe x/y daca dreapta se afla de la i la i + dx/dy
int SolveMinX()
{
int nr = 0;
for(int i = 0; i <= NMax; i++)
X[i].sd = X[i - 1].sd + nr, nr += X[i].nr;
nr = 0;
for(int i = NMax; i >= 0; i--)
X[i].ds = X[i + 1].ds + nr, nr += X[i].nr;
int mini = X[0].sd + X[dx].ds;
for(int i = 1; i <= NMax; i++) {
///DP[i] = X[i].sd + X[i + dx].ds;
mini = min(X[i].sd + X[i + dx].ds, mini);
}
return mini;
}
int SolveMinY()
{
int nr = 0;
for(int i = 0; i <= NMax; i++)
Y[i].sd = Y[i - 1].sd + nr, nr += Y[i].nr;
nr = 0;
for(int i = NMax; i >= 0; i--)
Y[i].ds = Y[i + 1].ds + nr, nr += Y[i].nr;
int mini = Y[0].sd + Y[dy].ds;
for(int i = 1; i <= NMax; i++) {
///DP[i] = Y[i].sd + Y[i + dy].ds;
mini = min(Y[i].sd + Y[i + dy].ds, mini);
}
return mini;
}
int main()
{
fin >> N >> dx >> dy;
for(int i = 0; i < N; i++) {
fin >> x >> y;
X[x].nr++, Y[y].nr++;
}
fout << SolveMinX() + SolveMinY() << '\n';
fin.close();
fout.close();
return 0;
}