Cod sursa(job #1151537)

Utilizator YoChinezuWeng Mihai Alexandru YoChinezu Data 24 martie 2014 10:51:31
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const double eps=1.e-4;

struct point{
    double x,y;
};

bool cmp(point a,point b)
{
    if(fabs(a.x-b.x)>=eps)
        return a.x<b.x;
    return a.y<b.y;
}

point v[1005];
int rasp;

bool binar(point x,int n)
{
    int s,d,m;
    s=1;
    d=n;
    while(s<=d)
    {
        m=s+(d-s)/2;
        if(fabs(v[m].x-x.x)<eps&&fabs(v[m].y-x.y)<eps)
            return 1;
        if(cmp(x,v[m]))
            d=m-1;
        else
            s=m+1;
    }
    return 0;
}

int main(){
    freopen("patrate3.in", "r", stdin);
    freopen("patrate3.out", "w", stdout);
    int n,i,j;
    point a,b;
    double aux,auy;
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        scanf("%lf%lf",&aux,&auy);
        v[i].x=aux;
        v[i].y=auy;
    }
    
    sort(v+1,v+n+1,cmp);
    
    for(i=1;i<n;++i){
        for(j=i+1;j<=n;++j){
            a.x=v[i].x+v[i].y-v[j].y;
            a.y=v[i].y+v[j].x-v[i].x;
            b.x=v[i].y+v[j].x-v[j].y;
            b.y=v[j].x+v[j].y-v[i].x;
            if(binar(a,n)&&binar(b,n)){
                rasp++;
            }
        }
    }
    
    printf("%d\n",rasp/2);
    
    return 0;
}