Cod sursa(job #2199840)

Utilizator AndreiVisoiuAndrei Visoiu AndreiVisoiu Data 29 aprilie 2018 12:10:16
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

ifstream in("patrate3.in");
ofstream out("patrate3.out");

const int maxN = 1001;
const double eps = 1e-4;

struct punct {
    double x, y;
};

punct p[maxN];
int n;

bool eg(const double &a, const double &b) {
    return abs(a-b) < eps;
}

bool pEg(const punct &a, const punct &b) {
    return eg(a.x, b.x) && eg(a.y, b.y);
}

bool comp(const punct &a, const punct &b) {
    if(eg(a.x, b.x))
        return a.y < b.y;
    else return a.x < b.x;
}


bool cb(const punct &a) {
    int st = 1, dr = n;
    while(st <= dr) {
        int m = (st+dr)/2;
        if(pEg(p[m], a)) return true;
        if(eg(a.x, p[m].x))
            if(p[m].y < a.y) st = m+1;
            else dr = m-1;
        else
            if(p[m].x < a.x) st = m+1;
            else dr = m-1;
    }
    return false;
}

int main()
{
    int sol = 0;
    in >> n;
    for(int i = 1; i <= n; i++)
        in >> p[i].x >> p[i].y;
    sort(p+1, p+n+1, comp);
    for(int i = 1; i < n; i++) {
        for(int j = i+1; j <= n; j++) {
            punct a, b, m;
            m.x = (p[i].x + p[j].x)/2;
            m.y = (p[i].y + p[j].y)/2;

            double cx = m.x - p[i].x,
                   cy = m.y - p[i].y;
            if(p[i].y < p[j].y) {
                a.x = m.x - cy;
                a.y = m.y + cx;

                b.x = m.x + cy;
                b.y = m.y - cx;
            } else {
                a.x = m.x + cy;
                a.y = m.y + cx;

                b.x = m.x - cy;
                b.y = m.y - cx;
            }

            if(!pEg(p[i], a) && !pEg(p[i], b) && !pEg(p[j], a) && !pEg(p[j], b))
                if(cb(a) && cb(b)) sol++;
        }
    }

    out << sol;
    return 0;
}