Cod sursa(job #1448053)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 5 iunie 2015 23:37:00
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 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);

  nSlopes = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      addSlope(&v[i], &v[j], nSlopes++);
    }
  }
  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;
}