Cod sursa(job #2348443)

Utilizator alexradu04Radu Alexandru alexradu04 Data 19 februarie 2019 18:43:08
Problema Patrate 3 Scor 100
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.39 kb
#include <bits/stdc++.h>
#define eps 1e-12
using namespace std;
int ans,n;
struct Gigel
{
    double x,y;
};
Gigel v[1005];
bool mic (Gigel a,Gigel b)
{
    return a.x!=b.x ? a.x<b.x : a.y<b.y;
}
bool cmp (Gigel a, Gigel b)
{
    if(a.x==b.x)
    {
        return a.y>b.y;
    }
    return a.x>b.x;
}
bool egal(double x,double y)
{
    return abs(x-y)<eps;
}
int exist(Gigel p)
{
	int st=1,dr=n,mid=0;
	while(st<=dr)
	{
		mid=(st+dr)/2;
		if(egal(p.x,v[mid].x) && egal(p.y,v[mid].y))
            return 1;
		if(mic(v[mid],p))
            st=mid+1;
		else
            dr=mid-1;
	}
	return 0;
}
void check(Gigel a,Gigel b)
{
	Gigel m={(a.x+b.x)/2,(a.y+b.y)/2},d={0,0},t={0,0};
	double dx=abs(a.x-m.x),dy=abs(a.y-m.y);
	if(a.y<b.y)
	{
		d.x=m.x-dy;
		d.y=m.y+dx;
		t.x=m.x+dy;
		t.y=m.y-dx;
	}
	else
	{
		d.x=m.x-dy;
		d.y=m.y-dx;
		t.x=m.x+dy;
		t.y=m.y+dx;
	}
	if(exist(d)&&exist(t))
        ans++;
}
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);
        v[i].x=round(v[i].x*10000);
		v[i].y=round(v[i].y*10000);
    }
    sort(v+1,v+n+1,mic);
    for(int i=1;i<n;++i)
    {
        for(int j=i+1;j<=n;++j)
        {
            check(v[i],v[j]);
        }
    }
    printf("%d",ans/2);
    return 0;
}