Cod sursa(job #1409703)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 30 martie 2015 17:52:29
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<fstream>
#include<algorithm>
using namespace std;
int n, m, i, nr, j, ii, jj, c1, c2, nr1;
long long d;
pair<int, int> p[1002];

struct dr{
   int x;
   int y;
};

dr v[500010];
ifstream fin("trapez.in");
ofstream fout("trapez.out");
long long det(int X1, int Y1, int X2, int Y2, int X3, int Y3){
    return (X3 - X1) * 1LL * (Y2 - Y1) - (X2 - X1) * 1LL * (Y3 - Y1);
}

int cmp(dr a, dr b){
    return det(0, 0, a.x, a.y, b.x, b.y) <= 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++){
            m++;
            v[m].x = p[j].first - p[i].first;
            v[m].y = p[j].second - p[i].second;
        }
    }

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

    nr1 = 1;
    for(i = 2; i <= m; i++){
        if (det(0, 0, v[i].x, v[i].y, v[i-1].x, v[i-1].y) == 0)
            nr1++;
        else {
            nr += nr1 * (nr1 - 1) / 2;
            nr1 = 1;
        }
    }
    nr += nr1 * (nr1 - 1) / 2;

    fout<< nr <<"\n";
    return 0;
}