Cod sursa(job #2067542)

Utilizator Andreiii500Andrei Puiu Andreiii500 Data 16 noiembrie 2017 16:27:29
Problema Trapez Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include<algorithm>
#include<iostream>
#include<fstream>
using namespace std;

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

struct pct{
    long long y,x;
};

struct panta{
    long long index1, index2;
    long long dy, dx;
};

long long abss(long long x){
    if(x < 0) return -x;
    return x;
}

long long comparPante(panta a, panta b){
    if(a.dx == 0) return 0;
    if(b.dx == 0) return 1;

    long long produs1 = abss(a.dx * b.dy);
    long long produs2 = abss(b.dx * a.dy);

    long long semn1 = (a.dx * a.dy)>0?1:-1;
    long long semn2 = (b.dx * b.dy)>0?1:-1;

    produs1 *= semn1;
    produs2 *= semn2;

    return produs1 < produs2;
}

long long panteEgale(panta a, panta b){
    if(a.dx == 0 && b.dx == 0) return 1;
    else if(a.dx == 0 || b.dx == 0) return 0;

    long long produs1 = abss(a.dx * b.dy);
    long long produs2 = abss(b.dx * a.dy);

    long long semn1 = (a.dx * a.dy)>0?1:-1;
    long long semn2 = (b.dx * b.dy)>0?1:-1;

    produs1 *= semn1;
    produs2 *= semn2;

    return produs1 == produs2;
}

const long long N = 1000;
panta pante[N*N];
pct puncte[N];
long long n,nPante;

int main()
{
    in>>n;
    for(long long i=0; i<n; ++i)
        in>>puncte[i].x>>puncte[i].y;

    nPante = 0;
    for(long long i=0; i<n; ++i)
        for(long long j=i+1; j<n; ++j){
            pante[nPante].index1 = i;
            pante[nPante].index2 = j;
            pante[nPante].dx = (puncte[j].x - puncte[i].x);
            pante[nPante].dy = (puncte[j].y - puncte[i].y);
            ++nPante;
        }

    ///for(long long i=0; i<nPante; ++i) cout<<pante[i].index1<<" "<<pante[i].index2<<" "<<(1.0 * pante[i].dy / pante[i].dx)<<"\n"; cout<<"\n";

    sort(pante, pante+nPante, comparPante);

    ///for(long long i=0; i<nPante; ++i) cout<<pante[i].index1<<" "<<pante[i].index2<<" "<<(1.0 * pante[i].dy / pante[i].dx)<<"\n"; cout<<"\n";

    long long cntPanteEgale = 1;
    long long cntTrapeze = 0;
    for(long long i=1; i<nPante; ++i)
    {
        long long panteleSuntEgale = panteEgale(pante[i-1], pante[i]);
        if(panteleSuntEgale)
            ++cntPanteEgale;

        if(!panteleSuntEgale || i == nPante-1){
            cntTrapeze += cntPanteEgale * (cntPanteEgale-1) / 2;
            cntPanteEgale = 1;
        }
    }
    out<<cntTrapeze;

    return 0;
}