Cod sursa(job #1448056)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 5 iunie 2015 23:44:17
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>

#define MAX_N 1000
#define INF 2000000000
#define EPS 1e-14

typedef struct {
  int x, y;
} point;

double slopes[(MAX_N * (MAX_N - 1) >> 1) + 1];

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++) {
      slopes[nSlopes++] = (v[i].x == v[j].x) ? (INF + 1) : 1.00 * (v[j].y - v[i].y) / (v[j].x - v[i].x);
    }
  }
  std::sort(slopes, slopes + nSlopes);

  cnt = 0;
  int i = 0;
  slopes[nSlopes] = INF + 2; // santinela
  do {
    int j = i + 1;
    while (fabs(slopes[i] - slopes[j]) < EPS) {
      j++;
    }
    cnt += (j - i) * (j - i - 1) >> 1;
    i = j;
  } while (i < nSlopes);

  f = fopen("trapez.out", "w");
  fprintf(f, "%d\n", cnt);
  fclose(f);
  return 0;
}