Cod sursa(job #1448049)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 5 iunie 2015 23:35:27
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#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;
}