Cod sursa(job #768352)

Utilizator SteveStefan Eniceicu Steve Data 16 iulie 2012 17:36:33
Problema Patrate 3 Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

#define eps 0.00001
#define cf(a, b) (abs (a - b) <= eps)

typedef struct {
    float x;
    float y;
} cutzu;

int N;
cutzu v[1005];

inline int cmp (cutzu a, cutzu b) {
    if (cf(a.x, b.x)) return a.y < b.y;
    return a.x < b.x;
}

void Citire () {
    ifstream fin ("patrate3.in");
    fin >> N;
    for (int i = 0; i < N; i++)
    {
        fin >> v[i].x >> v[i].y;
    }
    sort (v, v + N, cmp);
    fin.close ();
}

int B_Search (float val1, float val2) {
    int i, step;
    for (step = 1; step < N; step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < N && (v[i + step].x < val1 || (cf(v[i + step].x, val1) && v[i + step].y <= val2))) i += step;
    if (cf(v[i].x, val1) && cf(v[i].y, val2)) return 1;
    return 0;
}

int Business () {
    float x3, y3, x2, y2;
    float xm, xf0, xf1, ym, yf0, yf1;
    int cnt = 0;
    for (int i = 0; i < N - 1; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            x2 = v[j].x; y2 = v[j].y; x3 = v[i].x; y3 = v[i].y;
            xm = x2 + x3; ym = y2 + y3;
            xf1 = (xm + y3 - y2) / 2;
            xf0 = xm - xf1;
            yf1 = (ym + x2 - x3) / 2;
            yf0 = ym - yf1;
            if (B_Search (xf0, yf0) && B_Search (xf1, yf1)) cnt++;
        }
    }
    return cnt;
}

void Scriere () {
    ofstream fout ("patrate3.out");
    fout << Business ();
    fout.close ();
}

int main () {
    Citire ();
    Scriere ();
    return 0;
}