Cod sursa(job #2072492)

Utilizator berindeiChesa Matei berindei Data 21 noiembrie 2017 21:44:40
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("trapez.in");
ofstream out("trapez.out");
int const INF=2e9;
double const eps=1e-10;
struct point{
    int x, y;
}puncte[1001];
struct fractie{
    int a, b;
}temp;
struct dreapta{
    fractie panta;
    int c;
}drepte[500001];
int cmmdc(int a, int b){
    if (b==0)
        return a;
    return cmmdc(b, a%b);
}
bool cmp(dreapta a, dreapta b){
    if (1.0*a.panta.a/a.panta.b<1.0*b.panta.a/b.panta.b) return true;
    else if (1.0*a.panta.a/a.panta.b==1.0*b.panta.a/b.panta.b)
        if (a.c<=b.c) return true;
    return false;
}
int main(){
    int n, i, j, lv=0, dx, dy, cmm, sti, li, dscz, 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++){
            lv++;
            dx=puncte[j].x-puncte[i].x;
            dy=puncte[j].y-puncte[i].y;
            cmm=cmmdc(dx, dy);
            dx/=cmm;
            dy/=cmm;
            if (dx)
                temp={dy, dx};
            else
                temp={INF, 1};
            drepte[lv].panta = temp;
            drepte[lv].c=puncte[i].x*dy -puncte[i].y*dx;
        }
    sort(drepte+1, drepte+lv+1, cmp);
    drepte[lv+1]={{INF, INF}, INF};
//    for (i=1; i<=lv; i++)
//        cout << drepte[i].panta.a << ' ' << drepte[i].panta.b << ' '<< drepte[i].c << endl;
    for (i=1; i<=lv; i++){
        sti=i;
        dscz=0;
        while (i<=lv && drepte[i].panta.a==drepte[i+1].panta.a && drepte[i].panta.b==drepte[i+1].panta.b){ ///cat timp sunt paralele
            li=i;
            while (i<=lv && drepte[i].c==drepte[i+1].c) i++; ///cat timp sunt identice
            dscz+=(i-li+1)*(i-li)/2;
            i++;
        }
        i--;
        trapeze+=(i-sti+1)*(i-sti)/2-dscz;
    }
    out << trapeze;
}