Cod sursa(job #1788896)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 26 octombrie 2016 16:17:57
Problema Patrate 3 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <cstdio>
#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const double EPS = 1e-4;

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

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

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 && v[i+step].x - x < EPS){
            i += step;
        }else if(i + step <= rg && fabs(v[i+step].x - x) <= EPS){
            if(v[i+step].y - y < EPS){
                i += step;
            }
        }
    }
    if(fabs(v[i].x - x) <= EPS && fabs(v[i].y - y) <= EPS){
        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;
    int ans = 0;
    for(i = 1;i <= n;i++){
        for(j = i+1;j <= n;j++){
            ok = true;
            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);
            if(ok == false){
                continue;
            }
            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/2);
    return 0;
}