Cod sursa(job #2321513)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 16 ianuarie 2019 10:37:42
Problema Trapez Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

struct segm
{
    int x1, x2, y1, y2;
};

int N, nrSegm;
long long sol;
pair <int, int> pts[1005];

segm v[500005];

inline bool cmp(const segm A, const segm B)
{
    long long dx1 = A.x2 - A.x1;
    long long dy1 = A.y2 - A.y1;
    long long dx2 = B.x2 - B.x1;
    long long dy2 = B.y2 - B.y1;

    return dy1 * dx2 < dy2 * dx1;
}

int main()
{
    fin >> N;

    for(int i = 1; i <= N; i++)
        fin >> pts[i].first >> pts[i].second;

    sort(pts + 1, pts + N + 1);

    for(int i = 1; i < N; i++)
        for(int j = i + 1; j <= N; j++)
        {
            v[++nrSegm].x1 = pts[i].first;
            v[nrSegm].x2 = pts[j].first;
            v[nrSegm].y1 = pts[i].second;
            v[nrSegm].y2 = pts[j].second;
        }

    sort(v + 1, v + nrSegm + 1, cmp);

    for(int i = 1; i < nrSegm; i++)
    {
        int k = 1;

        long long dx = v[i].x2 - v[i].x1;
        long long dy = v[i].y2 - v[i].y2;

        long long dxx = v[i + 1].x2 - v[i + 1].x1;
        long long dyy = v[i + 1].y2 - v[i + 1].y1;

        while(i + 1 <= nrSegm && dy * dxx == dyy * dxx)
        {
            k++;
            i++;

            dx = dxx;
            dy = dyy;
            dxx = v[i + 1].x2 - v[i + 1].x1;
            dyy = v[i + 1].y2 - v[i + 1].y1;
        }

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

    fout << sol;
    return 0;
}