Cod sursa(job #1153337)

Utilizator ionutpop118Pop Ioan Cristian ionutpop118 Data 25 martie 2014 13:30:18
Problema Patrate 3 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps=1.e-4;
struct point
{
    double x,y;
};
point v[1005];
int n;
bool cmp(point a,point b)
{
    if(fabs(a.x-b.x)<eps)
        return a.y<b.y;
    return a.x<b.x;
}
bool bs(point p)
{
    int st,dr,med;
    st=1;
    dr=n;
    while (st<=dr)
    {
        med=(st+dr)/2;
        if (fabs(v[med].x-p.x)<eps&&fabs(v[med].y-p.y)<eps)
            return 1;
        else
            if (!cmp(p,v[med]))
                st=med+1;
            else
                dr=med-1;
    }
    return 0;
}
bool valid(point a,point b)
{
    point x,y,m;
    m.x=(a.x+b.x)*0.5;
    m.y=(a.y+b.y)*0.5;
    x.x=m.x+fabs(m.y-a.y);
    y.x=m.x-fabs(m.y-a.y);
    x.y=m.y-fabs(m.x-a.x);
    y.y=m.y+fabs(m.x-a.x);
    if (bs(x)&&bs(y))
        return 1;
    return 0;
}
int main()
{
    freopen("patrate3.in","r",stdin);
    freopen("patrate3.out","w",stdout);
    int s;
    double x,y;
    scanf("%d",&n);
    for (register int i=1;i<=n;++i)
    {
        scanf("%lf%lf",&x,&y);
        v[i].x=x;
        v[i].y=y;
    }
    sort (v+1,v+n+1,cmp);
    s=0;
    for (register int i=1;i<=n;++i)
        for (register int j=i+1;j<=n;++j)
            s+=valid(v[i],v[j]);
    printf("%d",s);
    return 0;
}