Pagini recente » Cod sursa (job #2490499) | Cod sursa (job #3132629) | Cod sursa (job #3000619) | Cod sursa (job #901235) | Cod sursa (job #2292834)
#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];
inline latura make_latura(int x1, int y1, int x2, int y2) {
latura lat;
int aux;
// a doua coordonata trebuie sa fie mai mare pentru a face comparatia intre raporturi corecta
if (y1 > y2) {
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;
}
inline 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));
}
inline 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;
}