Cod sursa(job #1815504)

Utilizator zhm248Mustatea Radu zhm248 Data 25 noiembrie 2016 12:33:47
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int x[1001],y[1001];
struct dr
{
    int a,b;
};

long long cmmdc(long long a,long long b)
{
    while(b)
    {
        int r=a%b;
        a=b;
        b=r;
    }
    return a;
}

bool cmp(dr a,dr b)
{
    if(a.a==b.a)
        return a.b<b.b;
    else
        return a.a<b.a;
}

dr v[1000001];
int main()
{
    freopen("trapez.in","r",stdin);
    freopen("trapez.out","w",stdout);
    int n,i,j,nr=0,nr1=1,s=0;
    long long a,b,c,d,e;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
    {
        scanf("%d%d",&x[i],&y[i]);
    }
    for(i=1;i<n;++i)
    {
        for(j=i+1;j<=n;++j)
        {
            a=1LL*y[j]-1LL*y[i];
            b=1LL*x[i]-1LL*x[j];
            c=(1LL*x[j]*y[i])-(1LL*x[i]*y[j]);
            d=cmmdc(fabs(a),fabs(b));
            e=cmmdc(d,fabs(c));
            a/=e;
            b/=e;
            c/=e;
            if(a<0)
            {
                a*=(-1);
                b*=(-1);
            }
            v[++nr].a=(int)a;
            v[nr].b=(int)b;
        }
    }
    sort(v+1,v+nr+1,cmp);
    for(i=1;i<=nr;++i)
    {
        if(v[i].a==v[i+1].a&&v[i].b==v[i+1].b)
            nr1++;
        else
        {
            s+=(((nr1-1)*nr1)/2);
            nr1=1;
        }
    }
    printf("%d\n",s);
    return 0;
}