Cod sursa(job #532535)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 11 februarie 2011 21:17:29
Problema Arbori indexati binar Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <stdio.h>
#include <algorithm>
#include <set>
#define Nmax 200003
#define LL long long
using namespace std;

ofstream fout("pante.out");

int Arbi[Nmax];
int N; LL A,B,C,D,sol;
LL X[Nmax],Y[Nmax],S1[Nmax],S2[Nmax];
int ind1[Nmax],ind2[Nmax],wh[Nmax];

inline int cmp1(int i,int j){
     return ((S1[i] < S1[j]) || (S1[i]==S1[j] && S2[i]<S2[j]));
}
inline int cmp2(int i,int j){
    return ((S2[i] < S2[j]) || (S2[i]==S2[j] && i<j));
}

inline void Add(int i){
    int p,z=0;
    for(p=1; p<i; p<<=1);
    for( ; i<=N; ){
        Arbi[i]++;
        while( !( i & (1<<z) ) ) z++;
        i+=(1<<z);
        z++;
    }
}
inline int Query(int i){
    int p,z=0;
    for(p=1; p<i; p<<=1);
    for( ; i>0; ){
        sol+=Arbi[i];
        while( !( i & (1<<z) ) ) z++;
        i-=(1<<z);
        z++;
    }
}

int main(){
    int i,j,ii,poz,l,r,m,step,ss;
    freopen("pante.in","r",stdin);
    scanf("%d%d%d%d%d",&N,&A,&B,&C,&D);
    for(i=1;i<=N;++i){
        scanf("%d%d",&X[i],&Y[i]), ind1[i]=ind2[i]=i;
        S1[i]=A*X[i]-B*Y[i];
        S2[i]=D*Y[i]-C*X[i];
    }
    sort(ind1+1,ind1+N+1,cmp1);
    sort(ind2+1,ind2+N+1,cmp2);
    for( ss=1; ss<N; ss<<=1);

    for(i=1;i<=N;++i){
        ii=ind1[i];

        for(j=1,step=ss; step; step>>=1 )
            if( j+step <=N && S2[ind2[j+step]]<=S2[ii] )
                j+=step;

        Query(j);
        Add(j);
    }

    fout<<sol<<"\n";
    fclose(stdin); fout.close();
    return 0;
}