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;

}