Cod sursa(job #1077812)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 11 ianuarie 2014 17:59:33
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;

ifstream in("patrate3.in");
ofstream out("patrate3.out");

const int NMAX = 1001;
const double PREC = 0.001;

struct Point{
    double x, y;
}V[NMAX];


int N;

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

bool findPoint(const Point & searchedPoint)
{

    for(int left = 0,right = N - 1,middle; left <= right;)
    {
        middle = (left+right)/2;

        if(fabs(searchedPoint.x - V[middle].x) < PREC && fabs(searchedPoint.y - V[middle].y)  < PREC)
            return true;

        if(cmp(searchedPoint,V[middle]))
            right = middle-1;
        else
            left = middle+1;
    }

    return false;
}

int main()
{
    int i, j, counter = 0;
    double difx, dify;
    Point point1, point2;

    in >> N;

    for(i = 0; i < N; i++){
        in >> V[i].x >> V[i].y;
    }

    sort(V , V + N , cmp);

    for(i = 0; i < N; i++)
        for(j = i + 1; j < N; j++){

            Point center;

            center.x = ( V[i].x + V[j].x )/2;
            center.y = ( V[i].y + V[j].y )/2;

            difx = fabs(center.x - V[i].x);
            dify = fabs(center.y - V[i].y);
            // Sa notam dx = abs(mijx - x0) si dy = abs(mijy - y0).
            // Se observa ca daca y0 < y1 atunci x2 = mijx + dy, y2 = mijy - dx, x3 = mijx - dy iar y3 = mijy + dx.
            // In caz contrar, avem x2 = mijx - dy, y2 = mijy - dx, x3 = mijx + dy iar y3 = mijy + dx.

            if(V[i].y < V[j].y){
                point1.x = center.x + dify;
                point1.y = center.y - difx;

                point2.x = center.x - dify;
                point2.y = center.y + difx;
            }
            else {
                point1.x = center.x - dify;
                point1.y = center.y - difx;

                point2.x = center.x + dify;
                point2.y = center.y + difx;
            }

            if(findPoint(point1) && findPoint(point2))
                counter++;
        }

    out << counter/2 << '\n';

    return 0;
}