Cod sursa(job #514366)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 18 decembrie 2010 15:41:28
Problema Trapez Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

int x[1000001],y[1000001],z[1000001],v[2][1001],n,p,s,c;

int cmp(int i,int j)
{
    double ai=x[i]/(double)sqrt(x[i]*x[i]+y[i]*y[i]),aj=x[j]/(double)sqrt(x[j]*x[j]+y[j]*y[j]);
    return ai<aj;
}

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