# Poj Solution 3212

```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;

}

```
This entry was posted in poj. Bookmark the permalink.