Cod sursa(job #1081718)

Utilizator IoannaPandele Ioana Ioanna Data 13 ianuarie 2014 20:51:08
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 1000

using namespace std;

struct point {
    int x, y;
};

int n;
int nr = 0;
vector<point> p;

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

void read() {
    in>>n;
    long double x, y;
    point pct;
    for (int i = 0; i < n; i++) {
        in>>x>>y;
        pct.x = x * 100000; // cu 10000 ca sa trec de zecimale si cu inca 10 pt div 2
        pct.y = y * 100000;
        p.push_back(pct);
    }
}

bool comparare(const point a, const point b) {
    if (b.x > a.x || (b.x == a.x && b.y > a.y))
        return true;
    return false;
}

bool found(point a) {
    int st = 0;
    int dr = n - 1;
    int mij;
    while (st <= dr) {
        mij = (st + dr) / 2;
        if (p[mij].x < a.x || (p[mij].x == a.x && p[mij].y < a.y)) {
            st = mij + 1;
            continue;
        }
        if (p[mij].x > a.x || (p[mij].x == a.x && p[mij].y > a.y)) {
            dr = mij - 1;
            continue;
        }
        return true;
    }
    return false;
}

void solve() {
    point a, b;//punctele pe care le caut
    point m, h;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            m.x = (p[i].x + p[j].x) / 2;
            m.y = (p[i].y + p[j].y) / 2;
            h.x = (p[i].x - p[j].x) / 2;
            h.y = (p[i].y - p[j].y) / 2;
            a.x = m.x - h.y;
            a.y = m.y + h.x;
            b.x = m.x + h.y;
            b.y = m.y - h.x;
            if (found(a) && found(b)) {
                nr++;
            }
        }
    }
}

int main() {
    read();
    sort(p.begin(), p.end(), comparare);
    solve();
    out<<nr;
    return 0;
}