Cod sursa(job #365280)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 18 noiembrie 2009 12:23:09
Problema Trapez Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include<stdio.h>
#include<math.h>
#define EPS 0.001
#define INF 2000000000.0
#define ll long long
struct POINT
{
    double x,y;
};

struct LINE
{
    POINT A,B;
};

int verticalp(POINT A, POINT B)
{
    return (fabs(A.x-B.x)<EPS);
}

int verticall(LINE l)
{
    return (fabs(l.A.x-l.B.x)<EPS);
}

double panta(LINE l)
{
    if(verticall(l))return INF;
    else
        return ((l.B.y-l.A.y)/(l.B.x-l.A.x));
}

int n,i,a[1005][5],j,tr,u,ok,nr;
double v[250001],ul,aux;
int partitionare (int st,int dr)
{
    int i,j,m;
    double pivot,aux;
    m=(st+dr)/2;
    pivot=v[m];
    i=st-1;
    j=dr+1;
    while(1)
    {
        do{++i;}while(v[i]<pivot);
        do{--j;}while(v[j]>pivot);
        if(i<j)
        {
            aux=v[i];
            v[i]=v[j];
            v[j]=aux;
            
        } //if
        else
	        return j;
    }//while
}//func

void quick(int st,int dr)
{
    int p;
    if(st<dr)
    {
        p=partitionare(st,dr);
        quick(st,p);
        quick(p+1,dr);
    }//if
}

int main ()
{
    POINT A,B;
    LINE l;
    freopen("trapez.in","r",stdin);
    freopen("trapez.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
	    scanf("%d%d",&a[i][1],&a[i][2]);
    for(i=1;i<=n-1;i++)
        for(j=i+1;j<=n;j++)
	    {
	        A.x=a[i][1];A.y=a[i][2];
	        B.x=a[j][1];B.y=a[j][2];
	        l.A=A;l.B=B;
	        v[++u]=panta(l);
	    }
    quick(1,u);
    ul=v[1];tr=1;
    for(i=2;i<=u;i++)
        if(v[i]!=ul)
        {
            nr+=(ll)tr*(tr-1)/2;
            ul=v[i];
            tr=1;
        }
        else
            tr++;
    printf("%d",nr);
    return 0;
}