Cod sursa(job #355074)

Utilizator daniel.dumitranDaniel Dumitran daniel.dumitran Data 10 octombrie 2009 10:09:43
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define FISIN     "triang.in"
#define FISOUT    "triang.out"

FILE *fin, *fout;

#define MAXN 1500
#define EPS 0.0001

struct point {
  double x, y;
} p[MAXN];

double dist(const point& a, const point& b) {
  double dx = a.x - b.x;
  double dy = a.y - b.y;
  return sqrt(dx * dx + dy * dy);
}

int n, nrt;

struct wpoint {
  point p;
  double w;
} wp[MAXN];

int comp_wpoint(const void* a, const void* b) {
  const wpoint& p1 = *(wpoint*)a;
  const wpoint& p2 = *(wpoint*)b;
  
  if (p1.w < p2.w) return -1;
  if (p1.w > p2.w) return 1;
  return 0;
}

int main() {
  fin = fopen(FISIN, "rt");
  fout = fopen(FISOUT, "wt");

  fscanf(fin, "%d", &n);
  for (int i = 0; i < n; ++i)
    fscanf(fin, "%lf %lf", &p[i].x, &p[i].y);

  for (int i = 0; i < n; ++i) {
    int m = 0;
    for (int j = i + 1; j < n; ++j, ++m) {
      wp[m].p = p[j];
      wp[m].w = dist(p[i], p[j]);
    }

    qsort(wp, m, sizeof(wpoint), comp_wpoint);

    int last = 0;
    for (int j = 0; j < m; ++j) {
      while (j < m && (wp[j].w - wp[last].w < EPS)) ++j;
      for (int k1 = last; k1 < j; ++k1)
        for (int k2 = k1 + 1; k2 < j; ++k2)
          if (fabs(dist(wp[k1].p, wp[k2].p) - wp[k1].w) < EPS)
            nrt++;
      last = j;
    }
  }
  
  fprintf(fout, "%d\n", nrt);

  fclose(fout);
  fclose(fin);
  return 0;
}