Cod sursa(job #423085)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 23 martie 2010 15:03:18
Problema Patrate 3 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include<stdio.h>
FILE *f=fopen("patrate3.in","r");
FILE *g=fopen("patrate3.out","w");
struct point{
	 float x;
	 float y;
} v[1001];
int n,i,j,nr;
float xp1,xp2,yp1,yp2,dx,dy,mijx,mijy;
int tx,ty;
void schimb(int a, int b){
   float t=v[a].x;
   v[a].x=v[b].x;
   v[b].x=t;
   t=v[a].y;
   v[a].y=v[b].y;
   v[b].y=t;	
}
void sort(){
 for(int i=1;i<=n;i++)
   for(j=1;j<i;j++)
    if(v[i].x < v[j].x  || (v[i].x==v[j].x && v[i].y < v[j].y ))
	  schimb(i,j);	

}
int cauta(float x,float y){
	int p=1;
	int u=n;
	int mij=0;
	while(p<=u){
		mij=(p+u)/2;
	
		if((v[mij].x -x < 0.0001 && v[mij].x -x > -0.0001) && (v[mij].y -y < 0.0001 && v[mij].y -y> -0.0001))
			return 1;
				else //am gasit valoarea
		if(v[mij].x<x)
		 p=mij+1;
		else if(v[mij].x > x)
		 u=mij-1;
		else if(v[mij].y < y)
			p=mij+1;
		else if(v[mij].y > y)
			u=mij-1;
		
	}

return 0;
}
int main(){
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
	fscanf(f,"%f%f",&v[i].x,&v[i].y);
sort();	
for(i=1;i<=n;i++)
  for(j=1;j<i;j++)
  { mijx = (v[i].x + v[j].x) / 2;
    mijy = (v[i].y + v[j].y) / 2;
	dx=mijx - v[j].x;
	dy=mijy - v[j].y;
	if(dx<0)
		dx=-dx;
	if(dy<0)
		dy=-dy;
	dx*=100000;
	tx=(int)dx;
	dx=(float)tx/100000;
	dy*=100000;
	ty=(int)dy;
	dy=(float)ty/100000;
	if(v[i].y - v[j].y > 0.0001 || v[i].y - v[j].y < -0.0001){
		xp1 = mijx + dy;
		yp1 = mijy - dx;
		xp2 = mijx - dy;
		yp2 = mijy + dx;
		
	}
	
	else {
		xp1 = mijx - dy;
		yp1 = mijy - dx;
		xp2 = mijx + dy;
		yp2 = mijy + dx;
	
	}
	if(cauta(xp1,yp1)&&cauta(xp2,yp2))
		 nr++;	  
  }
fprintf(g,"%d",nr);
return 0;	
}