Cod sursa(job #1047981)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 5 decembrie 2013 02:09:21
Problema Patrate 3 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<fstream>
#include<algorithm>
#include<cmath>
#define dim 1002
using namespace std;

ifstream f("patrate3.in");
ofstream g("patrate3.out");
double midx,midy,Dx,Dy;
int n,i,j,cnt;
typedef struct pnt{
	double x,y;
};
pnt v[dim],x2,x3;
int cmp(pnt a,pnt b){
	if(fabs(a.x-b.x)<0.0001)
		return a.y<b.y;
	return a.x<b.x;
}
int bs(	pnt X  ) {
	int st,dr,mid;
	st=1;dr=n;
	
	while(	st<=dr	) {
		
		mid=(st+dr)/2;
		if(fabs(X.x-v[mid].x)<0.0001 && fabs(X.y-v[mid].y)<0.0001) 
			return 1;
		if( cmp (X,v[mid]) )
			dr=mid-1;
		else
			st=mid+1;
		
	}
	return 0;
}
int main () {
	
	f>>n;
	
	
	for(i=1;i<=n;++i)
		f>>v[i].x>>v[i].y;
	
	sort(v+1,v+1+n,cmp);
	for(i=1;i<n;++i){
		for(j=i+1; j<=n;++j) {
			
			midx=(v[i].x+v[j].x)/2;
			midy=(v[i].y+v[j].y)/2;
			Dx=fabs(midx-v[i].x);
			Dy=fabs(midy-v[i].y);
			
			if(v[i].y<v[j].y) {
				
				x2.x=midx+Dy;
				x2.y=midy-Dx;
				x3.x=midx-Dy;
				x3.y=midy+Dx;
				
				if(bs(x2)&&bs(x3)) ++cnt;
			}
			else {
				x2.x=midx-Dy;
				x2.y=midy+Dx;
				x3.x=midx-Dy;
				x3.y=midy+Dx;
				
				if(bs(x2)&&bs(x3)) ++cnt;
			}
		}
	}
	g<<cnt;
	
	return 0;
}