Cod sursa(job #1409649)

Utilizator robx12lnLinca Robert robx12ln Data 30 martie 2015 17:16:57
Problema Trapez Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int n, i, j, sol, nr, k;
pair<int, int> p[1010], a, b;
pair<int, int> v[500010];

int det(int x1, int y1, int x2, int y2, int x3, int y3) {
    return (x3-x1)*(y2-y1) - (x2-x1)*(y3-y1);
}

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

int main() {
    fin>>n;

    for (i=1;i<=n;i++)
        fin>>p[i].first>>p[i].second;

    sort(p+1, p+n+1);

    for (i=1;i<n;i++)
        for (j=i+1;j<=n;j++) {
            a = p[i];
            b = p[j];
            b.first -= a.first;
            b.second -= a.second;
            v[++k] = b;
        }

    sort(v+1, v+k+1, cmp);

    nr = 1;
    for (i=2;i<=k;i++)
        if (det(0, 0, v[i-1].first, v[i-1].second, v[i].first, v[i].second) == 0)
            nr++;
        else {
            sol += nr*(nr-1)/2;
            nr = 1;
        }
    sol += nr*(nr-1)/2;

    fout<<sol;
    return 0;
}