Cod sursa(job #1452293)

Utilizator hrazvanHarsan Razvan hrazvan Data 20 iunie 2015 15:08:45
Problema Triang Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <stdio.h>
#include <math.h>
#define MAXN 1500
#define EPS 0.001
#define INF 2000000000
typedef struct{
  double x, y;
}punct;
int point[MAXN];
punct v[MAXN];

inline char cmp(punct a, punct b){
  if(a.x - b.x < -EPS)
    return 0;
  if(a.x - b.x > EPS)
    return 2;
  if(a.y - b.y < -EPS)
    return 0;
  if(a.y - b.y > EPS)
    return 2;
  return 1;
}

void qs(int st, int dr){
  int i = st, j = dr, aux;
  punct pi;
  pi.x = v[point[(st + dr) / 2]].x;
  pi.y = v[point[(st + dr) / 2]].y;
  while(i <= j){
    while(cmp(pi, v[point[i]]) == 2)
      i++;
    while(cmp(v[point[j]], pi) == 2)
      j--;
    if(i <= j){
      aux = point[i];  point[i] = point[j];  point[j] = aux;
      i++;  j--;
    }
  }
  if(st < j)
    qs(st, j);
  if(i < dr)
    qs(i, dr);
}

inline punct lipsa(punct a, punct b){
  punct rez;
  double f, g, l = sqrt((a.y - b.y) * (a.y - b.y) + (a.x - b.x) * (a.x - b.x)), h = l * sqrt(3) / 2, dx;
  if(a.y == b.y){
    rez.x = -INF;
    rez.y = -INF;
  }
  else  if(a.x == b.x){
    rez.x = (a.x + b.x) / 2;
    rez.y = h;
  }
  else{
    f = -(b.x - a.x) / (b.y - a.y);
    dx = sqrt((h * h) / (f * f + 1));
    rez.x = (a.x + b.x) / 2 + dx;
    rez.y = (a.y + b.y) / 2 + dx * f;
    if(cmp(b, rez) == 2){
      rez.x = (a.x + b.x) / 2 - dx;
      rez.y = (a.y + b.y) / 2 - dx * f;
      if(cmp(b, rez) == 2){
        rez.x = -INF;
        rez.y = -INF;
      }
    }
  }
  return rez;
}

inline char caut(int st, int dr, punct a){
  int i = st - 1, pas = 1 << 10;
  while(pas > 0){
    if(i + pas <= dr && cmp(a, v[point[i + pas]]) == 2)
      i += pas;
    pas >>= 1;
  }
  if(i < dr && cmp(a, v[point[i + 1]]) == 1)
    return 1;
  return 0;
}

int main(){
  FILE *in = fopen("triang.in", "r");
  int n, i;
  fscanf(in, "%d", &n);
  for(i = 0; i < n; i++){
    fscanf(in, "%lf%lf", &v[i].x, &v[i].y);
    point[i] = i;
  }
  fclose(in);
  qs(0, n - 1);
  int j, rez = 0;
  punct x;
  for(i = 0; i < n; i++){
    for(j = i + 1; j < n; j++){
      x = lipsa(v[point[i]], v[point[j]]);
      if(!(x.x == -INF && x.y == -INF))
        rez += caut(j + 1, n - 1, x);
    }
  }
  FILE *out = fopen("triang.out", "w");
  fprintf(out, "%d", rez);
  fclose(out);
  return 0;
}