Cod sursa(job #1207588)

Utilizator tudormaximTudor Maxim tudormaxim Data 13 iulie 2014 14:18:28
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#define x first
#define y second
#define pair pair<int, int>
#define EPS 0.00000000001
#define INF 0x3f3f3f3f
using namespace std;
ifstream in("trapez.in");
ofstream out("trapez.out");
vector< pair > v;
vector<double> p;
int n, cnt;

double Paralela( pair i , pair j )
{
    if ( i.x == j.x ) return INF;
    if ( i.y == j.y ) return 0;
    return 1. * (j.y - i.y) / (j.x - i.x);
}

int main()
{
    in >> n;
    v.resize( n + 1 );
    for ( int i = 1; i <= n; i++ )
    {
        in >> v[i].x >> v[i].y;
        for ( int j = i - 1; j >= 1; j-- )
            p.push_back( Paralela( v[i], v[j] ) );
    }
    sort( p.begin(), p.end() );
    int s = 0, q;
    for ( int i = 0; i < p.size(); i++ )
    {
        q = i;
        if ( abs( p[i+1] - p[i] ) < EPS ) s++;
        else
        {
            cnt += ( s * ( s + 1 ) ) / 2;
            s = 0;
        }
    }
    cnt += ( s * ( s + 1 ) ) / 2;
    if ( q != p.size() - 1 )
    {
        s = p.size() - q - 1;
        cnt += ( s * ( s + 1 ) ) / 2;
    }

    out << cnt;

    in.close();
    out.close();
    return 0;
}