Cod sursa(job #2072659)

Utilizator berindeiChesa Matei berindei Data 22 noiembrie 2017 01:13:21
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("trapez.in");
ofstream out("trapez.out");
int const INF=2e9;
struct point{
    int x, y;
}puncte[1001];
struct dreapta{
    double panta, c;
}drepte[500001];
bool cmp(dreapta a, dreapta b){
    if (a.panta<b.panta) return true;
    else if (a.panta==b.panta)
        if (a.c<b.c) return true;
    return false;
}
int main(){
    int i, n, l=0, j, sti, dscz, li, trapeze=0;
    in >> n;
    for (i=1; i<=n; i++)
        in >> puncte[i].x >> puncte[i].y;
    for (i=1; i<=n; i++)
        for (j=i+1; j<=n; j++){
            drepte[++l].panta = (puncte[j].x-puncte[i].x) ? (double)(puncte[j].y-puncte[i].y)/(puncte[j].x-puncte[i].x) : INF;
            drepte[l].c=(drepte[l].panta!=INF) ? puncte[i].y-drepte[l].panta*puncte[i].x : puncte[i].x;
        }
    sort (drepte+1, drepte+l+1, cmp);
    drepte[l+1]={-INF, 0};
    for (i=1; i<=l; i++){
        sti=i;
        dscz=0;
        while (i<=l && drepte[i].panta==drepte[i+1].panta){ ///cat timp sunt paralele
            li=i;
            while (i<=l && drepte[i].c==drepte[i+1].c) i++; ///cat timp sunt identice
            dscz+=(i-li+1)*(i-li)/2;
            if (drepte[i].panta==drepte[i+1].panta) i++;
        }
        trapeze+=(i-sti+1)*(i-sti)/2-dscz;
    }
    out << trapeze;
}