Cod sursa(job #1815495)

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

int cmmdc(int a,int 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,a,b,d,nr=0,nr1=1,maxim=1;
    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=y[j]-y[i];
            b=x[i]-x[j];
            d=cmmdc(fabs(a),fabs(b));
            a/=d;
            b/=d;
            if(a<0)
            {
                a*=(-1);
                b*=(-1);
            }
            v[++nr].a=a;
            v[nr].b=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
        {
            if(maxim<nr1)
                maxim=nr1;
            nr1=1;
        }
    }
    printf("%d\n",(maxim*(maxim-1))/2);
    return 0;
}