Cod sursa(job #423255)

Utilizator laurpoppopescu laurentiu laurpop Data 23 martie 2010 17:56:56
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
FILE *f=fopen("patrate3.in","r");
FILE *g=fopen("patrate3.out","w");
struct point{
	 float x;
	 float y;
} v[10001];
int n,i,j,nr;
float xp1,xp2,yp1,yp2,dx,dy,mijx,mijy,t;
int tx,ty;
void schimb(int a, int b){ //interschimbam v[a] cu v[b]
   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(){
 int i,j;
 for(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 )) //sortam dupa x, in caz de egalitate dupa y
	  schimb(i,j);	//interschimbam v[i] cu v[j]

}
int cauta(float x,float y){
	int p=1;
	int u=n;
	int mij=0;
	while(p<=u){
		mij=(p+u)/2;	
		if( fabs(v[mij].x -x)< 0.00001 && fabs(v[mij].y -y)< 0.00001) //daca sunt egale, am gasit valoarea cautata
			return 1;
		else 
			if(v[mij].x<x) // valoarea x cautata mai mare decat cea curenta
			 p=mij+1;
		else 
			if(v[mij].x > x) // valoarea x cautata mai mica decat cea curenta
			 u=mij-1;
		else 
			if(v[mij].y < y) // valoarea y cautata mai mare decat cea curenta
			p=mij+1;
		else 
			if(v[mij].y > y) // valoarea y cautata mai mica decat cea curenta
			u=mij-1;
		
	}

return 0;
}
int fct(point a,point b){
	if(a.x<=b.x)
		 return 1;
	  else
		   if(a.x==b.x)
			   if(a.y<=b.y) return 1;
		   else return 0;
			   else 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(v+1,v+n+1,fct);	
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=fabs(mijx - v[j].x);
	dy=fabs(mijy - v[j].y);
//	if(dx<0)
	//	dx=-dx;
	//if(dy<0)
	//	dy=-dy;
	if( fabs(v[i].y - v[j].y)> 0.00001){
		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;	
}