Pagini recente » Cod sursa (job #1719288) | Cod sursa (job #1567) | Cod sursa (job #39814) | Cod sursa (job #3269086) | Cod sursa (job #2627424)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("tribute.in");
ofstream out("tribute.out");
const int dim = 50005;
int dx,dy,n,cate_x[dim],cate_y[dim],dp_x[dim],dp_y[dim],sume_x[dim],sume_y[dim];
pair<int,int> a[dim];
int Dist(int x_punct, int y_punct,int x_start,int y_start)
{
int distanta = 0;
if (y_start >= y_punct)
{
distanta += (y_start - y_punct);
if (x_start >= x_punct)
{
distanta += (x_start - x_punct);
}
else
{
if (x_start + dx >= x_punct)
{
distanta += (x_start + dx - x_punct);
}
}
}
if (y_start + dy <= y_punct)
{
distanta += (y_punct - y_start - dy);
if (x_start >= x_punct)
{
distanta += (x_start - x_punct);
}
else
{
if (x_start + dx >= x_punct)
{
distanta += (x_start + dx - x_punct);
}
}
}
if (y_start <= y_punct && y_punct <= y_start + dy)
{
if (x_start >= x_punct)
{
distanta += (x_start - x_punct);
}
else
{
if (x_start + dx >= x_punct)
{
distanta += (x_start + dx - x_punct);
}
}
}
return distanta;
}
int main()
{
in >> n >> dx >> dy;
for (int i=1; i<=n; i++)
{
in >> a[i].first >> a[i].second;
cate_x[a[i].first]++;
cate_y[a[i].second]++;
}
sume_x[0] = cate_x[0];
sume_y[0] = cate_y[0];
for (int i=1; i<dim; i++)
{
sume_x[i] = cate_x[i] + sume_x[i-1];
sume_y[i] = cate_y[i] + sume_y[i-1];
}
for (int i=dx+1; i<dim; i++) dp_x[0] += cate_x[i]*(i - dx);
for (int i=dy+1; i<dim; i++) dp_y[0] += cate_y[i]*(i - dy);
int mini_x = dp_x[0];
int mini_y = dp_y[0];
for (int i=1; i<dim; i++)
{
dp_x[i] = dp_x[i-1] - (sume_x[dim-1] - sume_x[min(i+dx-1, dim-1)]) + (sume_x[max(0, i - 1)]);
///cout << dp_x[i] << " ";
mini_x = min(mini_x, dp_x[i]);
}
///cout << "\n";
for (int i=1; i<dim; i++)
{
dp_y[i] = dp_y[i-1] - (sume_y[dim-1] - sume_y[min(i+dy-1 ,dim-1)]) + (sume_y[max(0, i-1)]);
//cout << dp_y[i] << " ";
mini_y = min(mini_y, dp_y[i]);
}
out << mini_x + mini_y;
return 0;
}