Cod sursa(job #2458188)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 19 septembrie 2019 20:25:12
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
#include <cmath>
#include <algorithm>

#define EPS 0.00000000001
#define NMAX 1005
#define LIM 2000000005
using namespace std;

ifstream fin("trapez.in");
ofstream fout("trapez.out");

struct punct
{
    int x, y;
} v[NMAX];

struct chestie{
    int tip;
    double u;
}unghi[NMAX * NMAX];

inline bool cmp(chestie a, chestie b){
    if(abs(a.u - b.u) < EPS)
        return a.tip < b.tip;
    return a.u < b.u;
}

int main()
{
    int n;
    fin >> n;

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

    int cnt = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = i + 1; j <= n; ++j){
            if(v[i].x == v[j].x)
                unghi[++cnt].u = -LIM, unghi[cnt].tip = 3;
            else
            {
                unghi[++cnt].u = (abs(v[i].y - v[j].y) / (double)abs(v[i].x - v[j].x));
                punct a = v[i];
                punct b = v[j];
                if(a.y < b.y)
                    swap(a, b);
                if(a.x < b.x && a.y != b.y)
                    unghi[cnt].tip = 2;
                else unghi[cnt].tip = 1;
            }
        }
    sort(unghi + 1, unghi + cnt + 1, cmp);

    unsigned long long lg = 1, rez = 0;
    for(int i = 2; i <= cnt; ++i){
        if(unghi[i].u - unghi[i - 1].u < EPS && unghi[i].tip == unghi[i - 1].tip)
            ++lg;
        else {
            rez += (lg - 1) * lg / 2;
            lg = 1;
        }
    }
    rez += (lg - 1) * lg / 2;
    fout << rez << '\n';
    return 0;
}