Cod sursa(job #1579697)

Utilizator stoianmihailStoian Mihail stoianmihail Data 24 ianuarie 2016 23:02:24
Problema Patrate 3 Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <stdio.h>
#include <math.h>

#define Nadejde 1000
#define MOD 8192

typedef struct {
  int x, y;
} pair;

typedef struct {
  pair place;
  int next;
} cell;

int N;
cell map[Nadejde + 1];
int hash[(MOD << 1) + 1];
#define hash (hash + MOD)

/** Insereaza perechea curenta (x, y). **/
void insert(int pos) {
  int h = map[pos].place.x % MOD;
  map[pos].next = hash[h];
  hash[h] = pos;
}

/** Verifica daca coordonatele A sunt egale cu coordonatele B. **/
int equal(pair A, pair B) {
  return ((A.x == B.x) && (A.y == B.y));
}

/** Cauta coordonatele (x, y) in tabela hash. **/
int find(int x, int y) {
  int pos, h = x % MOD;
  
  pair place;
  place.x = x, place.y = y;

  for (pos = hash[h]; (pos != 0) && (!equal(map[pos].place, place)); pos = map[pos].next);
  return pos;
}

int main(void) {
  int i, j, count = 0;
  double x, y;
  pair delta;
  FILE *f = fopen("patrate3.in", "r");
  
  /* Citirea datelor. */
  fscanf(f, "%d", &N);
  for (i = 1; i <= N; i++) {
    fscanf(f, "%lf %lf", &x, &y);
    map[i].place.x = (int)round(x * 10000);
    map[i].place.y = (int)round(y * 10000);
    insert(i);
  }
  fclose(f);

  /* Calcularea solutiei. */
  for (i = 1; i <= N; i++) {
    for (j = 1; j <= N; j++) {
      if (i != j) {
        delta.x = map[i].place.x - map[j].place.x;
        delta.y = map[j].place.y - map[i].place.y;
    
        if (find(map[i].place.x + delta.y, map[i].place.y + delta.x) && find(map[j].place.x + delta.y, map[j].place.y + delta.x)) {
          //fprintf(stderr, "intra");
          count++;
        }
      }
    }
  }

  /* Afisarea solutiei. */
  freopen("patrate3.out", "w", stdout);
  fprintf(stdout, "%d\n", count / 4);
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}