Cod sursa(job #1162195)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 31 martie 2014 18:15:37
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

const int Nmax = 1000;
const double EPS = 1e-9;

typedef long long ll;

struct Point
{
    double x, y;

    friend istream& operator >> ( istream &f, Point &P )
    {
        f >> P.x >> P.y;
        return f;
    }
};

int cmp( pair<int,int> a, pair<int,int> b )
{
    return a.first * b.second == a.second * b.first;
}

pair<int,int> slopes[Nmax * Nmax];
Point P[Nmax + 1];
int N;

int main()
{
    ifstream f("trapez.in");
    ofstream g("trapez.out");

    f >> N;

    for ( int i = 1; i <= N; ++i )
            f >> P[i];

    int M = 0;

    for ( int i = 1; i < N; ++i )
            for ( int j = i + 1; j <= N; ++j )
                    slopes[ ++M ] = pair<int,int>( P[i].x - P[j].x, P[i].y - P[j].y );

    sort( slopes + 1, slopes + 1 + M );

    pair<int,int> last_s = slopes[1];
    int contor = 1;
    ll sol = 0;

    for ( int i = 2; i <= M; ++i )
    {
        if ( cmp( last_s, slopes[i]) ) contor++;
        else
        {
            sol += 1LL * contor * ( contor - 1 ) / 2LL;
            contor = 1;
        }

        last_s = slopes[i];
    }

    sol += 1LL * contor * ( contor - 1 ) / 2LL;

    g << sol << "\n";

    return 0;
}