Cod sursa(job #1731937)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 20 iulie 2016 14:18:12
Problema Patrate 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>
#include <algorithm>
#define x first
#define y second
#define var 0.00001
using namespace std;

int N,Sol;
double DX,DY;
pair <double,double>v[1001],mij,P1,P2;
bool BS(double x,double y)
{
	int lw=1,mid,hi=N;
	while(lw<=hi)
	{
		mid=(hi+lw)>>1;
		if(abs(x-v[mid].x)<=var&&abs(y-v[mid].y)<=var)
			return true;
		else if(x>v[mid].x||(abs(x-v[mid].x)<=var&&y>v[mid].y))
			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("%lf %lf",&v[i].x,&v[i].y);
	sort(v+1,v+1+N);
	for(int i=1;i<=N;i++)
		for(int j=i+1;j<=N;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)
				P1.x=mij.x+DY,P1.y=mij.y-DX,P2.x=mij.x-DY,P2.y=mij.y+DX;
			else
				P1.x=mij.x-DY,P1.y=mij.y-DX,P2.x=mij.x+DY,P2.y=mij.y+DX;
			if(BS(P1.x,P1.y)&&BS(P2.x,P2.y))
				Sol++;
		}
	printf("%d",Sol/2);
    return 0;
}