Cod sursa(job #1891821)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 24 februarie 2017 12:49:43
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

const int INF = (1LL << 32) - 1;
const double eps = 1.e-14;

struct POINT {
    int x, y;
};

POINT a[1005];
vector <double> v;

int main() {
    freopen("trapez.in", "r", stdin);
	freopen("trapez.out", "w", stdout);

    int n;
    scanf("%d", &n);

    for(int i = 1; i <= n; ++ i) {
        int x, y;
        scanf("%d%d", &x, &y);
        a[i].x = x;
        a[i].y = y;
    }

    for(int i = 1; i < n; ++ i) {
        for(int j = i + 1; j <= n; ++ j) {
            double unghi;
            if(a[j].x - a[i].x == 0) {
                unghi = INF;
            } else {
                unghi = (double)(a[j].y - a[i].y) / (a[j].x - a[i].x);
            }
            v.push_back(unghi);
        }
    }

    sort(v.begin(), v.end());
    v.push_back(-1);

    long long rasp = 0;
    int lungime = 1;

    for(int i = 1; i < v.size(); ++ i) {
        if( fabs(v[i] - v[i - 1]) < eps && i != v.size() - 1 ) {
            ++ lungime;
        } else {
            rasp = rasp + ((long long) lungime * (lungime - 1)) / 2;
            lungime = 1;
        }
    }

    printf("%lld", rasp);

    return 0;
}