Cod sursa(job #1740431)

Utilizator mariusn01Marius Nicoli mariusn01 Data 11 august 2016 16:31:33
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
// se formeaza dreptele suport pentru orice pereche de cate 2 puncte si se sorteaza dupa panta
#include <fstream>
#include <algorithm>
#define DIM 1003
#define x first
#define y second

using namespace std;

pair<int, int> p[DIM], s[DIM*DIM], a, b, c;
int n, i, k, sol;

int cadran(const pair<int, int> &a) {
    if (a.y == 0)
        return 1;
    if (a.x == 0)
        return 2;
    if (a.x > 0)
        return 1;
    return 2;
}

long long det(const pair<int, int> &a, const pair<int, int> &b) {
    return 1LL*a.x*b.y - 1LL*a.y*b.x;
}

int cmp(const pair<int, int> &a, const pair<int, int> &b) {
    int ca = cadran(a);
    int cb = cadran(b);
    if (ca != cb)
        return ca < cb;
    else
        return det(a, b) > 0;
}

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

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

    for (int i=1;i<n;i++)
        for (int j=i+1;j<=n;j++) {
            a = p[i];
            b = p[j];
            if (a.y > b.y || ( a.y == b.y && a.x > b.x )) {
                c = a;
                a = b;
                b = c;
            }
            s[++k] = make_pair(b.x-a.x, b.y-a.y);
        }

    sort(s+1, s+k+1, cmp);
    int L = 1;
    for (i=2;i<=k;i++)
        if (det(s[i], s[i-1]) == 0)
            L++;
        else {
            sol += L*(L-1)/2;
            L = 1;
        }
    sol += L*(L-1)/2;
    fout<<sol;
    return 0;
}