Cod sursa(job #268009)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 28 februarie 2009 17:20:48
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<algorithm>
#include<complex>
using namespace std;
short n;
double x[1001],y[1001];
int comp(double nr1,double nr2){
	if(fabs(nr1-nr2)<0.00001)
		return 1;
	return 0;}
int cautbin(double nrx,double nry){
	int st,dr,m;
	for(st=1,dr=n; st<=dr; ){
		m=(st+dr)/2;
		if(comp(x[m],nrx)){
			if(comp(y[m],nry))
				return 1;
			else if(y[m]<nry)
				st=m+1;
			else if(y[m]>nry)
				dr=m-1;}
		else if(x[m]<nrx)
			st=m+1;
		else if(x[m]>nrx)
			dr=m-1;}
	return 0;}
void sort(){
	int i,j;
	double aux;
	for(i=1; i<n; ++i)
		for(j=i+1; j<=n; ++j)
			if(x[i]>x[j]){
				aux=x[i];
				x[i]=x[j];
				x[j]=aux;
				aux=y[i];
				y[i]=y[j];
				y[j]=aux;}
			else if(comp(x[i],x[j])&&y[i]>y[j]){
				aux=y[i];
				y[i]=y[j];
				y[j]=aux;}}
void solve(){
	int i,j,k;
	double dx,dy,mijx,mijy;
	scanf("%hd",&n);
	for(i=1; i<=n; ++i)
		scanf("%lf%lf",&x[i],&y[i]);
	sort();
	for(i=1,k=0; i<n; ++i)
		for(j=i+1; j<=n; ++j){
			mijx=(x[i]+x[j])/2;
			mijy=(y[i]+y[j])/2;
			dx=fabs(mijx-x[i]);
			dy=fabs(mijy-y[i]);
			if((y[i]<y[j]&&cautbin(mijx+dy,mijy-dx)&&cautbin(mijx-dy,mijy+dx))||(y[i]>=y[j]&&cautbin(mijx-dy,mijy-dx)&&cautbin(mijx+dy,mijy+dx)))
				++k;}
	printf("%d",k/2);}
int main(){
	freopen("patrate3.in","r",stdin);
	freopen("patrate3.out","w",stdout);
	solve();
	return 0;}