Cod sursa(job #1409330)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 30 martie 2015 14:43:13
Problema Trapez Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<fstream>
#include<algorithm>
using namespace std;
int n, m, i, nr, j, ii, jj, c1, c2, d;
pair<int, int> p[1002];
struct dr{
   int x;
   int y;
};
dr v[1000000];
ifstream fin("trapez.in");
ofstream fout("trapez.out");
int det(dr a, dr b){
    return  a.x * b.y - a.y * b.x;
}
int cadran(dr a){
    if(a.y > 0){
        return 1;
    }
    else{
        return 2;
    }
}
int cmp(dr a, dr b){
    int c1 = cadran(a);
    int c2 = cadran(b);
    if(c1 == c2){
        int d = det(a, b);
        return d < 0;
    }
    return c1 < c2;
}
int main(){
    fin>> n;
    for(i = 1; i <= n; i++){
        fin>> p[i].first >> p[i].second;
    }
    for(i = 1; i < n; i++){
        for(j = i + 1; j <= n; j++){
            m++;
            ii = i;
            jj = j;
            if(p[ii].first > p[jj].first){
                swap(ii, jj);
            }
            v[m].x = p[jj].first - p[ii].first;
            v[m].y = p[jj].second - p[ii].second;
        }
    }
    sort(v + 1, v + m + 1, cmp);
    for(i = 1; i < m; i++){
        c1 = cadran(v[i]);
        c2 = cadran(v[i+1]);
        if(c1 == c2){
            d = det(v[i], v[i+1]);
            if(d == 0){
                nr++;
            }
        }
    }
    fout<< nr <<"\n";
    return 0;
}