Cod sursa(job #223096)

Utilizator mihaipoascaPoasca Mihai mihaipoasca Data 26 noiembrie 2008 21:46:10
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<stdio.h>
FILE *fin=fopen("trapez.in","r"),
    *fout=fopen("trapez.out","w");

double p[4000005];
int x[1001],y[1001],N;

long long fact(long long x){
    if(x==0) return 0;
    long long aux=1;
    for(long long i=1;i<=x;i++)
        aux*=i;
    return aux;
}

void swap(int i,int j){
    double aux;
    aux=p[i];p[i]=p[j];p[j]=aux;
}

int main(){
    fscanf(fin,"%d",&N);
    for(int i=1;i<=N;i++)
        fscanf(fin,"%d %d",&x[i],&y[i]);
    int Nh=0;
    long long r=0;
    for(int i=1;i<N;i++)
        for(int j=i+1;j<=N;j++){
            if(y[i]!=y[j]){
                ++Nh;
                int k=Nh;
                p[k]=(double)(x[i]-x[j])/(y[i]-y[j]);
                while(k/2 && p[k/2] < p[k]){
                    swap(k,k/2);
                    k>>=1;
                }
            }
            else
                ++r;
        }

    int N=Nh;
    while(Nh>1){
        swap(1,Nh);
        Nh--;

        int nod=1,fiu;
        while(1){
            fiu=2*nod;
            if(fiu>Nh) break;
            if(fiu+1<=Nh && p[fiu+1]>p[fiu]) fiu++;
            if(p[fiu]<p[nod]) break;
            swap(fiu,nod);
            nod=fiu;
        }
    }
/*
    for(int i=1;i<=N;i++)
        fprintf(fout,"%llf ",p[i]);
*/
    long long cnt=fact(r-1);
    r=0;
    for(int i=2;i<=N;i++){
        if(p[i]==p[i-1])
            ++r;
        else{
            cnt+=fact(r);
            r=0;
        }
    }
    fprintf(fout,"%lld\n",cnt);
    fclose(fin);
    fclose(fout);
    return 0;
}