Cod sursa(job #474039)

Utilizator daniel.dumitranDaniel Dumitran daniel.dumitran Data 2 august 2010 04:00:20
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <stdio.h>
#include <stdlib.h>

#include <map>

#define MAXN 1000

FILE *f;

int n;
int x[MAXN], y[MAXN];

std::map<std::pair<int, int>, int> lines;

int main() {
  f = fopen("trapez.in", "rt");
  fscanf(f, "%d", &n);
  for (int i = 0; i < n; ++i)
    fscanf(f, "%d %d", x + i, y + i);
  fclose(f);

  for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j) {
      int dx = x[i] - x[j];
      int dy = y[i] - y[j];
      
      int a = abs(dx), b = abs(dy);
      while (b) {
	int r = a % b;
	a = b; b =r;
      }
      dx /= a; dy /= a;

      if (dx < 0) { dx *= -1; dy *= -1;}
      ++lines[std::make_pair(dx, dy)];
    }

  int res = 0;
  for (std::map<std::pair<int, int>, int>::const_iterator
	 it = lines.begin(); it != lines.end(); ++it) {
    int no = it->second;
    res += no * (no - 1) / 2;
  }
  
  f = fopen("trapez.out", "wt");
  fprintf(f, "%d\n", res);
  fclose(f);

  return 0;
}