Cod sursa(job #1788731)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 26 octombrie 2016 12:38:52
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

struct thing{
    double x,y;
}v[1005];

int compara (double a,double b)
{
    if (fabs (a-b)<=0.00001)
        return 1;
    return 0;
}

bool comp(thing a, thing b){
    if(a.x == b.x){
        return a.y < b.y;
    }
    return a.x < b.x;
}

bool binarySearch(int lf, int rg, double x, double y){
    int i,step;
    for(step = 1;step <= rg;step <<= 1);
    for(i = lf-1;step;step >>= 1){
        if(i + step <= rg && compara(v[i + step].x, x) && compara(v[i + step].y, y)){
            i += step;
        }
    }
    if(v[i].x == x && v[i].y == y){
        return 1;
    }
    return 0;
}

int main(){
    freopen("patrate3.in", "r", stdin);
    freopen("patrate3.out", "w", stdout);
    int n,i,j;
    double x,y;
    scanf("%d", &n);
    for(i = 1;i <= n;i++){
        scanf("%lf %lf", &v[i].x, &v[i].y);
    }
    sort(v + 1, v + n + 1, comp);
    bool ok = false;
    int ans = 0;
    for(i = 1;i <= n;i++){
        for(j = i+1;j <= n;j++){
            ok = false;
            x = (v[i].x + v[j].x + v[i].y - v[j].y)/2.0;
            y = (v[i].y + v[j].y + v[j].x - v[i].x)/2.0;
            ok |= binarySearch(1, n, x, y);
            x = (v[i].x + v[j].x + v[j].y - v[i].y)/2.0;
            y = (v[i].y + v[j].y + v[i].x - v[j].x)/2.0;
            ok |= binarySearch(1, n, x, y);
            if(ok){
                ans++;
            }
        }
    }
    printf("%d", ans);
    return 0;
}