Cod sursa(job #1648214)

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

int N,Sol;
vector < pair <int,int> > V;
vector < pair <int,int> > P;

bool Compare( pair <int,int> a , pair <int,int> b )
{
    if( a.first == b.first )
        return ( a.second < b.second );
    return ( a.first < b.first );
}

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 x,y;    fin>>x>>y;
        V.push_back(make_pair(x,y));
    }

    sort(V.begin(),V.end(),Compare);
}

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

            int n = GCD(x,y);

            int a = x / n;
            int b = y / n;

            P.push_back(make_pair(a,b));
        }

    sort(P.begin(),P.end(),Compare);

    int k = 1;

    for(int i=0;i<P.size()-1;++i)
        if(P[i].first == P[i+1].first && P[i].second == P[i+1].second)  k++;
        else
        {
            Sol += k*(k-1)/2;
            k = 1;
            fout<<Sol<<" ";
        }
    Sol += k*(k-1)/2;
}

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

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

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