Cod sursa(job #1307792)

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

struct Point
{
    int x, y;
};

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;
        a[i].x *= 10000;
        a[i].y *= 10000;
    }
    f.close();

    quickSort(0, N - 1, a);

    int dX, dY, midX, midY, x2, y2, x3, y3;
    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)
            {
                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;
            }

            Point p2, p3;
            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;
    g.close();

    return 0;
}

void quickSort(int left, int right, Point a[])
{
    int i = left, j = right;
    Point pivot = a[(left + right) / 2];
    int aux;
    while (i <= j)
    {
        while (a[i].x < pivot.x)
            i++;
        while (a[j].x > pivot.x)
            j--;
        if (i <= j)
        {
            if (a[i].x == a[j].x)
            {
                if (a[i].y > a[j].y)
                    swap(i, j, a);
                i++;
                j--;
            }
            else
            {
                swap(i, j, a);
                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 (a[middle].x == p.x)
        {
            if (a[middle].y == p.y)
                found = true;
            else if (a[middle].y < p.y)
                left = middle + 1;
            else
                right = middle - 1;
        }
        else if (a[middle].x < p.x)
            left = middle + 1;
        else
            right = middle - 1;
    }

    if (found)
        return 1;

    return 0;
}