Cod sursa(job #585237)

Utilizator darrenRares Buhai darren Data 28 aprilie 2011 17:51:02
Problema Patrate 3 Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <cmath>
#include <fstream>
#include <algorithm>
#include <utility>

using namespace std;

#define x first
#define y second

const double eps = 0.00000001;

int N;
pair<double, double> P[1002];
int squares;

int main()
{
    ifstream fin("patrate3.in");
    ofstream fout("patrate3.out");

    fin >> N;
    for (int i = 1; i <= N; ++i)
        fin >> P[i].x >> P[i].y;
    sort(P + 1, P + N + 1);

    int maxgo;
    for (maxgo = 1; (maxgo << 1) <= N; maxgo <<= 1);

    for (int i = 1; i < N; ++i)
        for (int j = i + 1; j <= N; ++j)
        {
            pair<double, double> mid;
            mid.x = P[i].x + P[j].x, mid.x /= 2;
            mid.y = P[i].y + P[j].y, mid.y /= 2;

            pair<double, double> dist, point1, point2;

            dist.x = mid.x - P[i].x;
            dist.y = mid.y - P[i].y;

            point1.x = mid.x - dist.y;
            point1.y = mid.y + dist.x;
            point2.x = mid.x + dist.y;
            point2.y = mid.y - dist.x;

            bool found = true;

            int step = maxgo, now;
            for (now = 0; step; step >>= 1)
                if (now + step <= N && (P[now + step].x < point1.x || (fabs(P[now + step].x - point1.x) < eps && P[now + step].y - point1.y < eps)))
                    now += step;
            found &= (fabs(P[now].x - point1.x) < eps && fabs(P[now].y - point1.y) < eps);

            step = maxgo;
            for (now = 0; step; step >>= 1)
                if (now + step <= N && (P[now + step].x < point2.x || (fabs(P[now + step].x - point2.x) < eps && P[now + step].y - point2.y < eps)))
                    now += step;
            found &= (fabs(P[now].x - point2.x) < eps && fabs(P[now].y - point2.y) < eps);

            squares += found;
        }

    fout << squares / 2;

    fin.close();
    fout.close();
}