Cod sursa(job #1048190)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 5 decembrie 2013 15:28:34
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
#include <fstream>

const static int NMAX = 1001;
const static int MODULO = 666013;

using namespace std;

class Punct
{
public:
    double x , y;
    Punct(const double & x = 0, const double & y = 0)
    {
        this->x = x;
        this->y = y;
    }
    bool operator==(const Punct & other)
    {
        return (x == other.x && y == other.y);
    }
};

ifstream input("patrate3.in");
ofstream output("patrate3.out");
int nr_puncte;
Punct vect[NMAX];

bool cmp(const Punct & A , const Punct & B)
{
    if (fabs(A.x - B.x) >= 0.0001)
        return A.x < B.x;
    return A.y < B.y;
}

bool search_point(const Punct & punct)
{
    int left = 0,right = nr_puncte - 1,middle;

    while(left <= right)
    {
        middle = (left+right) >> 1;

        if(fabs(punct.x - vect[middle].x)<0.0001 && fabs(punct.y - vect[middle].y)<0.0001)
            return true;
        if(cmp(punct,vect[middle]))
            right = middle-1;
        else
            left = middle+1;
    }
    return false;
}

int main()
{
    input >> nr_puncte;
    for (int i = 0; i < nr_puncte ; i++)
    {
        input >> vect[i].x >> vect[i].y;
    }

	sort(vect , vect + nr_puncte , cmp);

    int nr_patrate = 0;
    Punct aux1 , aux2 , mid , diferenta;

    for (int i = 0; i < nr_puncte; i++)
        for (int j = i+1; j<nr_puncte; j++)
        {
            mid.x = (vect[i].x + vect[j].x) / 2;
            mid.y = (vect[i].y + vect[j].y) / 2;
            diferenta.x = fabs(mid.x - vect[i].x);
            diferenta.y = fabs(mid.y - vect[i].y);

            if(vect[i].y<vect[j].y)
            {
                aux1.x = mid.x + diferenta.y;
                aux1.y = mid.y - diferenta.x;
                aux2.x = mid.x - diferenta.y;
                aux2.y = mid.y + diferenta.x;
                if(search_point(aux1) && search_point(aux2)) nr_patrate++;
            }
            else
            {
                aux1.x=mid.x - diferenta.y;
                aux1.y=mid.y - diferenta.x;
                aux2.x=mid.x + diferenta.y;
                aux2.y=mid.y + diferenta.x;
                if(search_point(aux1) && search_point(aux2)) nr_patrate++;
            }
        }

    output << nr_patrate / 2;
    return 0;
}