Cod sursa(job #2292829)

Utilizator CristyXtremeSimion Cristian CristyXtreme Data 30 noiembrie 2018 00:44:35
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

struct latura {
    int x1, y1, x2, y2;
} laturi[499500];

struct punct {
    int x, y;
};

int ind[499500];

latura make_latura(int x1, int y1, int x2, int y2) {
    latura lat;
    int aux;
    if (x1 > x2) {
        aux = x1;
        x1 = x2;
        x2 = aux;
        aux = y1;
        y1 = y2;
        y2 = aux;
    }
    lat.x1 = x1;
    lat.y1 = y1;
    lat.x2 = x2;
    lat.y2 = y2;
    return lat;
}

bool comp(int i, int j) {
    return (1ll * (laturi[i].y2  - laturi[i].y1) * (laturi[j].x2 - laturi[j].x1)) < (1ll * (laturi[i].x2  - laturi[i].x1) * (laturi[j].y2  - laturi[j].y1));
}

bool egalitate(int i, int j) {
    return (1ll * (laturi[i].y2  - laturi[i].y1) * (laturi[j].x2 - laturi[j].x1)) == (1ll * (laturi[i].x2  - laturi[i].x1) * (laturi[j].y2  - laturi[j].y1));
}

int main() {
	freopen("trapez.in", "r", stdin);
	freopen("trapez.out", "w", stdout);
	int n, nr_laturi = 0, pante_egale;
	long long int sol = 0;
	scanf("%d", &n);
	punct puncte[n];
	for (int i = 0; i < n; i++)
        scanf("%d %d", &puncte[i].x, &puncte[i].y);
    // cream toate laturile posibile cu punctele date (fiecare combinatie de puncte)
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            laturi[nr_laturi++] = make_latura(puncte[i].x, puncte[i].y, puncte[j].x, puncte[j].y);
    for (int i = 0; i < nr_laturi; i++)
        ind[i] = i;
    // sortam laturile in functie de panta (raportul a fost transformat in produs pentru a lucra cu numere intregi)
    sort(ind, ind + nr_laturi, comp);
    int left = 0, right = 1;
    // verificam cate secvente de laturi consecutive cu aceeasi panta exista, atunci se pot forma nr*(nr-1)/2 combinatii de trapezuri intre aceste laturi
    while (right < nr_laturi) {
        pante_egale = 1;
        while (right < nr_laturi && egalitate(ind[left], ind[right])) {
            pante_egale++;
            right++;
        }
        sol += 1ll * pante_egale * (pante_egale - 1) / 2;
        left = right;
        right++;
    }
    printf("%lld", sol);
	return 0;
}