Cod sursa(job #2022897)

Utilizator victoreVictor Popa victore Data 17 septembrie 2017 17:07:18
Problema Patrate 3 Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<cstdio>
#include<algorithm>

using namespace std;

const int nmax=1005;
const double eps = 1e-5;

int n;

struct point
{
    int x,y;
}punct[nmax];


inline bool cmp(const point &p1, const point &p2)
{
    if(p1.x != p2.x)
        return p1.x < p2.x;

    return p1.y < p2.y;
}

inline bool check(int nr,int x,int y)
{
    return (punct[nr].x < x) || (punct[nr].x == x && punct[nr].y <= y);
}

inline bool BSearch(int x,int y)
{
    int i,step;

    for(step=1;step<n;step<<=1);

    for(i=1;step;step>>=1)
        if(i+step<=n && check(i+step,x,y))
            i+=step;

    return punct[i].x == x && punct[i].y == y;
}

int main()
{
    freopen("patrate3.in","r",stdin);
    freopen("patrate3.out","w",stdout);

    int i,j;

    double a,b;

    scanf("%d",&n);

    for(i=1;i<=n;++i)
    {
        scanf("%lf %lf",&a,&b);
        a+=eps;
        b+=eps;
        a*=10000;
        b*=10000;
        a*=2;
        b*=2;
        punct[i].x=a;
        punct[i].y=b;
    }

    sort(punct+1,punct+n+1,cmp);

    int midx,midy,dx,dy,sol=0;

    for(i=1;i<n;++i)
        for(j=i+1;j<=n;++j)
        {
            midx = ((punct[i].x + punct[j].x)>>1);
            midy = ((punct[i].y + punct[j].y)>>1);
            dx = midx - punct[i].x;
            dy = midy - punct[i].y;
            if(BSearch(midx - dy , midy + dx) && BSearch(midx + dy , midy - dx))
                ++sol;
        }

    printf("%d",(sol>>1));
}