http://poj.org/problem?id=3212
#include <stdio.h>
#include <memory.h>
#include <vector>
#include <algorithm>
using namespace std;
#define __int64 long long
const int size = 100010;
__int64 s[size];
int ss[size];
int m;
int pos[100100];
//���
void clear( )
{
memset( s, 0, sizeof s );
memset( ss, 0, sizeof ss );
}
inline int lowbit(int a)
{
return a&(a^(a-1));
}
//����a[y] = 1; Ҫ��y>=0
void set( int y, int key )
{
int j;
y++;
for(j=y;j<=m;j+=lowbit(j)) {
s[j] += key;
ss[j]++;
}
}
//����a[0,y]�ĺ�; y>=0
__int64 count(int y, int &count)
{
__int64 ans=0;
int j;
y++;
count = 0;
for(j=y;j>0;j-=lowbit(j)) {
ans+=s[j];
count += ss[j];
}
return ans;
}
struct point {
int x, y, id, X, Y;
}p[100000];
bool cmp( const point &a, const point &b ) {
return a.X < b.X || a.X == b.X && a.Y > b.Y;
}
inline void rotate( point &a ) {
int t = -a.y;
a.y = a.x;
a.x = t;
}
__int64 sum[100100];
int temp[100100];
int main()
{
int n, i, k, h;
scanf( "%d", &n );
for( i=0; i<n; i++ ) {
scanf( "%d%d", &p[i].x, &p[i].y );
p[i].id = i;
}
memset( sum, 0, sizeof sum );
for( k=0; k<4; k++ ) {
for( i=0; i<n; i++ ) {
p[i].X = p[i].x+p[i].y;
p[i].Y = 2000001-p[i].y+p[i].x;
temp[i] = p[i].Y;
}
sort( p, p+n, cmp );
sort( temp, temp+n );
m = std::uninitialized_copy( temp, temp+n, pos ) - pos;
clear( );
for( i=0; i<n; i++ ) {
int y = std::lower_bound( pos, pos+m, p[i].Y ) - pos;
sum[ p[i].id ] -= count( y, h );
sum[ p[i].id ] += (__int64)h*p[i].x;
set( y, p[i].x );
}
if( k < 3 ) {
for( i=0; i<n; i++ )
rotate( p[i] );
}
}
__int64 best = (__int64)1000000*n;
for( i=0; i<n; i++ )
if( sum[i] < best )
best = sum[i];
printf( "%I64dn", best );
return 0;
}