Cod sursa(job #2614862)

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

struct point {
    double x, y;
};

point p[MAX_N];

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

class myCompare {
public:
    bool operator()(const point&a, const point& b) {
        if(a.x < b.x)
            return true;
        if(a.x == b.x && a.y < b.y)
            return true;
        return false;
    }
};

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 x0, y0, x1, y1, 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, myCompare());
    ans = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = i + 1; j < n; ++j) {
            x0 = p[i].x;
            y0 = p[i].y;
            x1 = p[j].x;
            y1 = p[j].y;
            mx = (x0 + x1) / 2;
            my = (y0 + y1) / 2;
            dx = fabs(mx - x0);
            dy = fabs(my - y0);
            if(y0 < y1) {
                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);
            ok2 = bSearch(0, n - 1, x3, y3);
            if(ok1 && ok2)
                ++ans;
        }
    }
    fout << ans / 2 << "\n";
    fin.close();
    fout.close();
    return 0;
}