Pagini recente » Cod sursa (job #332646) | Cod sursa (job #2022842) | Cod sursa (job #1685537)
#include<iostream>
#include<fstream>
#include<vector>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
ifstream f("tribute.in");
ofstream g("tribute.out");
int AIB[150005], L[150005], C[150005];
int dx, dy, n;
long long sol;
int const oo = 1000000000;
void Read()
{
int i, x, y;
f>>n>>dx>>dy;
for(i=1; i<=n; i++){
f>>x>>y;
L[x+50002]++;
C[y+50002]++;
}
}
void Update(int pos, int val)
{
while(pos < 150005){
AIB[pos] += val;
pos += pos&(-pos);
}
}
int Query(int pos)
{
int sum = 0;
while(pos){
sum += AIB[pos];
pos -= pos&(-pos);
}
return sum;
}
void SolveL()
{
int i, pivot, st, dr, sum, trib, mini, ind;
for(i=1; i<150005; i++)
Update(i, L[i]);
mini = oo;
if(n % 2 == 1){
sum = 0;
for(i=1; sum <= (n/2); i++)
sum += C[i];
dr = i-1;
st = dr - dx;
for( ; st <= pivot; st++, dr++){
trib = abs(n - Query(dr) - Query(st - 1));
if(trib < mini){
mini = trib;
ind = st;
}
}
}
else{
sum = 0;
for(i=1; sum < (n/2); i++)
sum += C[i];
dr = i-1;
st = dr - dx;
sum = 0;
for(i=1; sum < (n/2)+1; i++)
sum += C[i];
pivot = i-1;
for( ; st < pivot; st++, dr++){
trib = abs(n - Query(dr) - Query(st - 1));
if(trib < mini){
mini = trib;
ind = st;
}
}
}
st = ind;
dr = ind + dx;
for(i=1; i<st; i++)
sol += L[i] * abs(st - i);
for(i=dr+1; i<150005; i++)
sol += L[i] * abs(dr - i);
}
void SolveC()
{
int i, pivot, st, dr, sum, trib, mini, ind;
for(i=1; i<150005; i++)
AIB[i] = 0;
for(i=1; i<150005; i++)
Update(i, C[i]);
mini = oo;
if(n % 2 == 1){
sum = 0;
for(i=1; sum <= (n/2); i++)
sum += C[i];
dr = i-1;
st = dr - dx;
for( ; st <= pivot; st++, dr++){
trib = abs(n - Query(dr) - Query(st - 1));
if(trib < mini){
mini = trib;
ind = st;
}
}
}
else{
sum = 0;
for(i=1; sum < (n/2); i++)
sum += C[i];
dr = i-1;
st = dr - dx;
sum = 0;
for(i=1; sum < (n/2)+1; i++)
sum += C[i];
pivot = i-1;
for( ; st <= pivot; st++, dr++){
trib = abs(n - Query(dr) - Query(st - 1));
if(trib < mini){
mini = trib;
ind = st;
}
}
}
st = ind;
dr = ind + dx;
for(i=1; i<st; i++)
sol += C[i] * abs(st - i);
for(i=dr+1; i<150005; i++)
sol += C[i] * abs(dr - i);
}
int main()
{
Read();
SolveL();
SolveC();
g<<sol<<"\n";
return 0;
}