Cod sursa(job #2614878)

Utilizator Horia14Horia Banciu Horia14 Data 12 mai 2020 19:44:57
Problema Patrate 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include<fstream>
#include<iostream>
#include<algorithm>
#include<cmath>
#define MAX_N 1000
#define EPS 1e-4
using namespace std;

struct point {
    double x, y;
};

point p[MAX_N];

inline bool egale(point a, point b) {
    return fabs(a.x - b.x) <= EPS && fabs(a.y - b.y) <= EPS;
}

inline bool cmp(point a, point b) {
    if(a.x < b.x)
        return true;
    else if(a.x == b.x && a.y < b.y)
        return true;
    return false;
}

inline bool bSearch(int l, int r, double a, double b) {
    int left, right, mid;
    left = l;
    right = r;
    point aux;
    aux.x = a;
    aux.y = b;
    while(left <= right) {
        mid = (left + right) >> 1;
        if(egale(p[mid], aux))
            return true;
        if(fabs(aux.x - p[mid].x) <= EPS) {
            if(p[mid].y < aux.y)
                left = mid + 1;
            else right = mid - 1;
        } else if(p[mid].x < aux.x)
            left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

int main() {
    int n, ans;
    double x2, y2, x3, y3, mx, my, dx, dy;
    bool ok1, ok2;
    ifstream fin("patrate3.in");
    ofstream fout("patrate3.out");
    fin >> n;
    for(int i = 0; i < n; ++i)
        fin >> p[i].x >> p[i].y;
    sort(p, p + n, cmp);
    ans = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = i + 1; j < n; ++j) {
            mx = (p[i].x + p[j].x) / 2;
            my = (p[i].y + p[j].y) / 2;
            dx = fabs(mx - p[i].x);
            dy = fabs(my - p[i].y);
            if(p[i].y < p[j].y) {
                x2 = mx + dy;
                y2 = my - dx;
                x3 = mx - dy;
                y3 = my + dx;
            } else {
                x2 = mx - dy;
                y2 = my - dx;
                x3 = mx + dy;
                y3 = my + dx;
            }
            ok1 = bSearch(0, n - 1, x2, y2);
            if(!ok1)
                continue;
            ok2 = bSearch(0, n - 1, x3, y3);
            if(!ok2)
                continue;
            ++ans;
        }
    }
    fout << ans / 2 << "\n";
    fin.close();
    fout.close();
    return 0;
}