Cod sursa(job #1308032)

Utilizator alexandru.ghergutAlexandru-Gabriel Ghergut alexandru.ghergut Data 3 ianuarie 2015 13:23:36
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <fstream>
#include <stdlib.h>
using namespace std;

struct Point
{
    double x, y;
};

int cmp(Point a, Point b);
void quickSort(int left, int right, Point a[]);
void swap(int i, int j, Point a[]);
bool binarySearch(int left, int right, Point a[], Point p);

int main()
{
    int N, i, j, k = 0;

    ifstream f("patrate3.in");
    f >> N;
    Point a[N];
    for (i = 0; i < N; i++)
        f >> a[i].x >> a[i].y;
    f.close();

    quickSort(0, N - 1, a);
    double midX, midY, dX, dY, x2, y2, x3, y3;
    Point p2, p3;
    for (i = 0; i < N - 1; i++)
        for (j = i + 1; j < N; j++)
        {
            midX = (a[i].x + a[j].x) / 2;
            midY = (a[i].y + a[j].y) / 2;
            dX = abs(a[i].x - midX);
            dY = abs(a[i].y - midY);
            if (a[i].y - a[j].y <= 0.0001)
            {
                x2 = midX + dY;
                y2 = midY - dX;
                x3 = midX - dY;
                y3 = midY + dX;
            }
            else
            {
                x2 = midX - dY;
                y2 = midY - dX;
                x3 = midX + dY;
                y3 = midY + dX;
            }


            p2.x = x2;
            p2.y = y2;
            p3.x = x3;
            p3.y = y3;

            if (binarySearch(0, N - 1, a, p2) && binarySearch(0, N - 1, a, p3))
                k++;
        }

    ofstream g("patrate3.out");
    g << k / 2;
    g.close();

    return 0;
}

int cmp(Point a, Point b) // returns 1 if higher, 0 if lower or equal
{
    if (abs(a.x - b.x) >= 0.0001)
        return a.x - b.x > 0.0001;
    return a.y - b.y > 0.0001;
}

void quickSort(int left, int right, Point a[])
{
    int i = left, j = right;
    Point pivot = a[(left + right) / 2];
    while (i <= j)
    {
        while (cmp(pivot, a[i]))
            i++;
        while (cmp(a[j], pivot))
            j--;
        if (i <= j)
        {
            swap (a[i], a[j]);
            i++;
            j--;
        }
    }

    if (left < j)
        quickSort(left, j, a);
    if (i < right)
        quickSort(i, right, a);
}

void swap(int i, int j, Point a[])
{
    int aux;

    aux = a[i].x;
    a[i].x = a[j].x;
    a[j].x = aux;

    aux = a[i].y;
    a[i].y = a[j].y;
    a[j].y = aux;
}

bool binarySearch(int left, int right, Point a[], Point p)
{
    bool found = false;
    int middle;
    while (left <= right && !found)
    {
        middle = (left + right) / 2;
        if (abs(a[middle].x - p.x) <= 0.0001 && abs(a[middle].y - p.y) <= 0.0001)
            found = true;
        else if (cmp(a[middle], p))
            right = middle - 1;
        else
            left = middle + 1;
    }

    if (found)
        return 1;

    return 0;
}