Cod sursa(job #1081733)

Utilizator IoannaPandele Ioana Ioanna Data 13 ianuarie 2014 21:04:35
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define NMAX 1000

using namespace std;

struct point {
    int x, y;
};

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

void read() {
    scanf("%d",&n);
    char nr[20];
    long double x, y;
    point pct;
    for (int i = 0; i < n; i++) {
        pct.x = pct.y = 0;

        scanf("%s", nr);
        int sgn = 1;
        if (nr[0] == '-')
            sgn = -1;
        else pct.x = nr[0] - '0';
        for (int i = 1; i < strlen(nr); i++) {

            if (nr[i] == '.') continue;
            pct.x = pct.x * 10 + nr[i] - '0';
        }
        pct.x *= sgn;

        scanf("%s", nr);
        sgn = 1;
        if (nr[0] == '-')
            sgn = -1;
        else pct.y = nr[0] - '0';
        for (int i = 1; i < strlen(nr); i++) {
            if (nr[i] == '.') continue;
            pct.y = pct.y * 10 + nr[i] - '0';
        }
        pct.y *= sgn;

        pct.x *= 10; // cu 10000 ca sa trec de zecimale si cu inca 10 pt div 2
        pct.y *= 10 ;
        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() {
    freopen("patrate3.in", "r", stdin);
    freopen("patrate3.out", "w", stdout);
    read();
    sort(p.begin(), p.end(), comparare);
    solve();
    printf("%d", nr/2);
    return 0;
}