Cod sursa(job #768080)

Utilizator SteveStefan Eniceicu Steve Data 15 iulie 2012 21:48:27
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.36 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iostream>

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];
/*struct lolcomp {
    bool operator () (const cutzu a, const cutzu b) const
    {
        if (a.x == b.x) return a.y < b.y;
        return a.x < b.x;
    }
};*/

//map <cutzu, int, lolcomp> mp;

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;
//        mp[v[i]] = 1;
    }
    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 mijx, mijy, dx, dy, x3, y3, x2, y2;
    float dist, p2, a, b, xp, yp;
    float xm, xf0, xf1, ym, yf0, yf1;
    cutzu u, t;
    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;
            /*dist = sqrt ((v[i].x - v[j].x) * (v[i].x - v[j].x) + (v[i].y - v[j].y) * (v[i].y - v[j].y));
            p2 = (v[i].x - v[j].x) / (v[j].y - v[i].y);
            dist /= 2;
            b = dist / (sqrt (p2 * p2 + 1));
            a = b * p2;
            xp = (v[i].x + v[j].x) / 2;
            yp = (v[i].y + v[j].y) / 2;
            u.x = b + xp;
            u.y = a + yp;
            t.x = xp - b;
            t.y = yp - a;
            //cout << t.x << " " << t.y << "\n";
            if (mp[u] == 1 && mp[t] == 1) cnt++, cout << u.x << " " << u.y << "\n";
            if (B_Search (u.x, u.y) || B_Search (t.x, t.y)) cnt++, cout << u.x << " " << u.y << "\n";*/
            /*mijx = (v[i].x + v[j].x) / 2;
            mijy = (v[i].y + v[j].y) / 2;
            dx = abs (mijx - v[i].x);
            dy = abs (mijy - v[i].y);
            if (v[i].y < v[j].y)
            {
                x2 = mijx + dy;
                y2 = mijy - dx;
                x3 = mijx - dy;
                y3 = mijy + dx;
            }
            else
            {
                x2 = mijx - dy;
                y2 = mijy - dx;
                x3 = mijx + dy;
                y3 = mijy + dx;
            }
            u.x = x2;
            u.y = y2;
            t.x = x3;
            t.y = y3;*/
            //cout << xf0 << " " << yf0 << "\n";
            //if (xf0 == 91.32 && yf0 == 13.36) cout << "//";
            if (B_Search (xf0, yf0) && B_Search (xf0, yf0)) cnt++;
            //cout << x2 << " " << y2 << "\n";
        }
    }
    //cout << B_Search(91.32, 13.36);
    return cnt;
}

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

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