Cod sursa(job #150941)

Utilizator free_coderDancu Ioana free_coder Data 7 martie 2008 17:32:29
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <stdio.h>
#define DIM 1001

struct punct {
  double x,y;
};

typedef punct tip;


punct v[DIM];
punct ps, pd;


void cre(tip *v, long int n);
void corect(long int poz, tip *v, long int n);
void sort(tip *v, long int n);
int cautb(punct a, int p, int u);

int n,i,j,patrat;
double x,y,mx,my,dx,dy;

int maiMare(punct a, punct b){
  if (a.x>b.x) return 1;
  if ((a.x==b.x) && (a.y<b.y)) return 1;
  return 0;
}


int main(){
  FILE *f = fopen("patrate3.in","r");
  fscanf(f,"%d",&n);
  for (i=1;i<=n;i++){
    fscanf(f,"%lf %lf",&x,&y);
    v[i].x = x;
    v[i].y = y;
  }
  fclose(f);
  sort(v,n);

  for (i=1;i<n;i++)
    for (j=i+1;j<=n;j++) {
      mx = (v[i].x+v[j].x)/2;
      my = (v[i].y+v[j].y)/2;
      dx = (v[j].x-v[i].x)/2;
      dy = (v[i].y-v[j].y)/2;
      ps.x = mx-dy;
      ps.y = my-dx;
      pd.x = mx+dy;
      pd.y = my+dx;

      if (cautb(ps,1,n)&&cautb(pd,1,n)) {
	patrat++;
      }

    }


  FILE *g = fopen("patrate3.out","w");

  fprintf(g,"%d",2*patrat);
  fclose(g);

  return 0;
}


int cautb(punct a, int p, int u){
  int m;
  while (p<=u) {
    m = (p+u)/2;
    if ((a.x==v[m].x)&&(a.y==v[m].y))
      return 1;
    else
      if ((a.x<v[m].x) || ((a.x==v[m].x) && (a.y>v[m].y)))
	u=m-1;
      else
	p=m+1;
  }
  return 0;
}



void cre(tip *v, long int n){
  long int i,c,p;
  tip aux;
  for (i=2;i<=n;i++) {
    c = i;
    p = i>>1;
    while ((p)&&maiMare(v[c],v[p])) {
      aux = v[c];
      v[c] = v[p];
      v[p] = aux;
      c = p;
      p = p>>1;
    }
  }
}

void corect(long int poz, tip *v, long int n){
  long int p,c;
  tip aux;
  p = poz;
  c = p<<1;
  while (c<=n) {
    if ((c+1<=n) && maiMare(v[c+1],v[c]))
      c++;
    if (maiMare(v[c],v[p])) {
      aux = v[c];
      v[c] = v[p];
      v[p] = aux;
      p = c;
      c = p<<1;
    } else break;
  }

}

void sort(tip *v, long int n) {
  long int i;
  tip aux;
  cre(v,n);
  for (i=n;i>1;i--) {
    aux = v[1];
    v[1] = v[i];
    v[i] = aux;
    corect(1,v,i-1);
  }
}