Pagini recente » Atasamentele paginii Clasament pregatire_2 | Monitorul de evaluare | Monitorul de evaluare | Istoria paginii utilizator/werz66 | Cod sursa (job #1448049)
#include <stdio.h>
#include <algorithm>
#define MAX_N 1000
#define INF 2000000000
#define ABS(A) ((A) < 0 ? -(A) : (A))
typedef struct {
int x, y;
} point;
typedef struct {
int numerator;
int denominator;
} fraction;
bool operator <(const fraction &a, const fraction &b) {
if (a.numerator == b.numerator) {
return a.denominator < b.denominator;
}
return a.numerator < b.numerator;
}
int gcd(int a, int b) {
if (!b) {
return a;
}
return gcd(b, a - a / b * b);
}
fraction slopes[MAX_N * MAX_N]; // cu santinela
inline void addSlope(point *A, point *B, int ptr) {
int num, den;
num = A->y - B->y;
den = A->x - B->x;
if (!den) { // vertical
num = INF;
den = 1;
} else { // fractie ireductibila
if (num < 0 && den < 0) {
num = -num;
den = -den;
}
int cmmdc = gcd(ABS(num), ABS(den));
num = num / cmmdc;
den = den / cmmdc;
}
slopes[ptr].numerator = num;
slopes[ptr].denominator = den;
}
int main(void) {
FILE *f = fopen("trapez.in", "r");
point v[MAX_N];
int n;
int nSlopes;
int cnt;
fscanf(f, "%d", &n);
for (int i = 0; i < n; i++) {
fscanf(f, "%d%d", &v[i].x, &v[i].y);
}
fclose(f);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
addSlope(&v[i], &v[j], n * i + j - 1);
}
}
nSlopes = n * (n - 1) / 2;
std::sort(slopes, slopes + nSlopes);
cnt = 0;
int i = 0;
slopes[nSlopes].numerator = INF + 1; // santinela
while (i < nSlopes) {
int j = i + 1;
while (slopes[j].numerator == slopes[i].numerator && slopes[j].denominator == slopes[i].denominator) {
j++;
}
cnt += (j - i - 1) * (j - i - 2) / 2;
i = j;
}
f = fopen("trapez.out", "w");
fprintf(f, "%d\n", cnt);
fclose(f);
return 0;
}