Cod sursa(job #1337451)

Utilizator retrogradLucian Bicsi retrograd Data 9 februarie 2015 00:37:25
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include<fstream>
#include<algorithm>
#include<utility>
#include<vector>
#include<cmath>

#define MAXN 1001
#define eps 1e-7

using namespace std;
typedef float var;

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

struct Point {
    var x, y;
    Point(var a, var b): x(a), y(b) {}
    Point() {}
};

var compare(pair<Point, Point> d1, pair<Point, Point> d2) {
    //Compara panta dreptei (a, b) cu cea a pantei (c, d)
    //Panta este (b.y-a.y)/(b.x-a.x)
    //(b.y-a.y)/(b.x-a.x) ~ (c.y-d.y)/(c.x-d.x)

    Point a = d1.first, b = d1.second, c = d2.first, d = d2.second;
    return -(b.y-a.y)*(c.x-d.x) + (b.x-a.x)*(c.y-d.y);
}

bool cmp(pair<Point, Point> d1, pair<Point, Point> d2) {
    return (compare(d1, d2) > 0);
}

Point POINTS[MAXN];
vector<pair<Point, Point> >DREPTE;
var n;


int main() {
    var x, y;

    fin>>n;
    for(int i=1; i<=n; i++) {
        fin>>x>>y;
        x /= 1000;
        y /= 1000;
        POINTS[i] = Point(x, y);
    }

    for(int i=1; i<n; i++) {
        for(int j=i+1; j<=n; j++) {
            if(POINTS[i].x < POINTS[j].x)
                DREPTE.push_back(make_pair(POINTS[i], POINTS[j]));
            else
                DREPTE.push_back(make_pair(POINTS[j], POINTS[i]));
        }
    }

    sort(DREPTE.begin(), DREPTE.end(), cmp);

    var sol = 0;

    for(var st=0; st<DREPTE.size()-1; ++st) {
        var dr = st+1;
        while(abs(compare(DREPTE[st], DREPTE[dr])) < eps) {
            dr++;
        }

        sol += (dr-st-1)*(dr-st)/2;
        st = dr-1;
    }

    fout<<sol;

    return 0;
}