Cod sursa(job #1731930)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 20 iulie 2016 13:46:21
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdio>
#include <algorithm>
using namespace std;

int N,Sol;
float DX,DY;
struct tab
{
    float x,y;
}v[1001],mij,ret;
tab third(int i,int j)
{
	mij.x=(v[i].x+v[j].x)/2;
	mij.y=(v[i].y+v[j].y)/2;
	DX=abs(mij.x-v[i].x);
	DY=abs(mij.y-v[i].y);
	if(v[i].y<v[j].y)
	{	ret.x=mij.x+DY;
		ret.y=mij.y-DX;
	}
	else
	{
		ret.x=mij.x-DY;
		ret.y=mij.y-DX;
	}
	return ret;
}
tab fourth(int i,int j)
{
	ret.x=mij.x-DY;
	ret.y=mij.y+DX;
	if(v[i].y<v[j].y)
	{	ret.x=mij.x-DY;
		ret.y=mij.y+DX;
	}
	else
	{
		ret.x=mij.x+DY;
		ret.y=mij.y+DX;
	}
	return ret;
}
bool cond(tab a,tab b)
{
	return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
bool Nearly(tab a,tab b)
{
	int x1=a.x*100000,y1=a.y*100000,x2=b.x*100000,y2=b.y*100000;
	if((x1==x2||x1==x2+1||x1==x2-1)&&(y1==y2||y1==y2+1||y1==y2-1))
		return true;
	else return false;
}
bool BS(tab val)
{
	int lw=1,hi=N,mid;
	while(lw<=hi)
	{
		mid=(lw+hi)>>1;
		if(Nearly(v[mid],val))
			return true;
		else if(cond(v[mid],val))
			lw=mid+1;
		else hi=mid-1;
	}
	return false;
}
int main()
{
    freopen("patrate3.in","r",stdin);
    freopen("patrate3.out","w",stdout);
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        scanf("%f%f",&v[i].x,&v[i].y);
	sort(v+1,v+1+N,cond);
	for(int i=1;i<=N;i++)
		for(int j=i+1;j<=N;j++)
			if(BS(third(i,j))&&BS(fourth(i,j)))
				Sol++;
	printf("%d",Sol/2);
    return 0;
}