Cod sursa(job #1648234)

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

int N,Sol,L1,L2;
struct Pair
{
    int x,y;
};
Pair V[1005],P[1000005];

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

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)
    {
        int a,b;    fin>>a>>b;  L1++;
        V[L1].x = a;
        V[L1].y = b;
    }

    sort(V+1,V+L1+1,Compare);
}

void Solve()
{
    for(int i=1;i<=L1;++i)
        for(int j=i+1;j<=L1;++j)
        {
            int x1 = V[i].x - V[j].x;  if(x1<0) x1*=-1;
            int y1 = V[i].y - V[j].y;  if(y1<0) y1*=-1;

            int n = GCD(x1,y1);

            int a = x1 / n;
            int b = y1 / n;

            L2++;

            P[L2].x = a;
            P[L2].y = b;
        }

    sort(P+1,P+L2+1,Compare);

    int k = 1;

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

void Print()
{
    fout<<Sol<<"\n";
}

int main()
{
    Read();
    Solve();
    Print();

    fin.close();
    fout.close();
    return 0;
}