Cod sursa(job #1026683)

Utilizator george_stelianChichirim George george_stelian Data 11 noiembrie 2013 21:31:37
Problema Trapez Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>
#include <cstdlib>

using namespace std;

struct punct
{
    float x,y;
};

punct v1[1000];
float v[500000],mid,aux;
long long int s;
int n,i,nr,x,j;

void sort(int st,int dr)
{
    int i=st,j=dr;
    mid=v[(i+j)/2];
    do
    {
        while(v[i]<mid) i++;
        while(v[j]>mid) j--;
        if(i<=j)
        {
            aux=v[i];v[i]=v[j];v[j]=aux;
            i++;j--;
        }
    }while(i<=j);
    if(i<dr) sort(i,dr);
    if(j>st) sort(st,j);
}

int main()
{
    freopen("trapez.in", "r", stdin);
    freopen("trapez.out", "w", stdout);
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d%d",&v1[i].x,&v1[i].y);
    nr=-1;
    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(v1[i].x==v1[j].x) s++;
            else
            {
                v[++nr]=(v1[j].y-v1[i].y)/(v1[j].x-v1[i].x);
            }
        }
    }
    s=s*(s-1)/2;
    sort(0,nr);
    x=1;
    for(i=1;i<=nr;i++)
    {
        if(v[i]==v[i-1]) x++;
        else
        {
            s+=x*(x-1)/2;
            x=1;
        }
    }
    s+=x*(x-1)/2;
    printf("%lld",s);
    return 0;
}