Cod sursa(job #1648849)

Utilizator cypry97Dascalitei Ciprian cypry97 Data 11 martie 2016 11:51:53
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

class punct
{
public:

    int x, y;

    punct(const int x = 0, const int y = 0):
        x(x), y(y)
    {}

    friend istream& operator>>(istream &is, punct &p)
    {
        is >> p.x >> p.y;
        return is;
    }

    friend ostream& operator<<(ostream &os, const punct &p)
    {
        os << p.x << ' ' << p.y;
        return os;
    }

};

class segment
{
public:

    int64_t dy, dx;

    segment(const punct &p1, const punct &p2):
        dy((int64_t)(p1.y - p2.y)), dx((int64_t)(p1.x - p2.x))
     {}

    bool operator<(const segment &seg) const
    {
        return dy * seg.dx < seg.dy * dx;
    }

    bool operator==(const segment &seg) const
    {
        return dy * seg.dx == seg.dy * dx;
    }
};

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

vector < punct > vector_puncte;
vector < segment > vector_segmente;
uint64_t raspuns;

void initializeaza()
{
    int n, i, j;

    fin >> n;
    vector_puncte.resize(n);
    vector_segmente.reserve((n*(n-1))/2);

    for(i = 0; i < n; i++)
        fin >> vector_puncte[i];

    for(i = 0; i < n; i++)
        for(j = i + 1; j < n; j++)
            if(vector_puncte[i].x > vector_puncte[j].x)
                vector_segmente.push_back(segment(vector_puncte[i], vector_puncte[j]));
            else
                vector_segmente.push_back(segment(vector_puncte[j], vector_puncte[i]));
}

void rezolva()
{
    vector < segment > :: iterator it_seg, it_inc;
    uint64_t numar;

    sort(vector_segmente.begin(), vector_segmente.end());
    it_inc = vector_segmente.begin();
    numar = 0;

    for(it_seg = vector_segmente.begin(); it_seg != vector_segmente.end(); it_seg++)
    {
        if(*it_seg == *it_inc)
            numar++;
        else
        {
            raspuns += (numar * (numar - 1)) / 2;

            it_inc = it_seg;
            numar = 1;
        }
    }
}

void afiseaza()
{
    fout << raspuns;
}

int main()
{
    initializeaza();
    rezolva();
    afiseaza();

    return 0;
}