Cod sursa(job #1650869)

Utilizator PaulStighiStiegelbauer Paul-Alexandru PaulStighi Data 11 martie 2016 21:10:02
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("trapez.in");
ofstream fout("trapez.out");

struct Pair
{
    int x,y;
};

int n,Sol;
Pair v[1005],panta[1000005];

bool Compare( Pair a , Pair b )
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}

int abs ( int a)
{
    if(a<0) return -a;
    return a;
}

int GCD ( int a , int b )
{
    if(!b)   return a;
    return GCD(b,a%b);
}

void Read()
{
    fin>>n;

    for(int i=1;i<=n;++i)
    {   fin>>v[i].x>>v[i].y;    }

    sort(v+1,v+n+1,Compare);
}

int main()
{
    Read();

    int k=0,l=1;

    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
        {
            int x1 = v[i].x - v[j].x;
            int y1 = v[i].y - v[j].y;
            int pa = GCD(abs(x1),abs(y1));
            k++;
            panta[k].x = x1/pa;
            panta[k].y = y1/pa;
        }

    sort(panta+1,panta+k+1,Compare);

    for(int i=1;i<k;i++)
        if(panta[i].x==panta[i+1].x&&panta[i].y==panta[i+1].y)  l++;
        else
        {
            Sol = Sol+l*(l-1)/2;
            l=1;
        }

    Sol = Sol+l*(l-1)/2;

    fout<<Sol<<"\n";
    return 0;
}