Cod sursa(job #1058945)

Utilizator miu_mik93FMI - Paduraru Miruna miu_mik93 Data 15 decembrie 2013 23:48:44
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 2.48 kb
#include <stdio.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <queue>
#include <cstdlib>
#include <iomanip>
#include <cmath>
using namespace std;
//#include <unordered_map>

#define NMAX 1001
#define ERROR 0.0001
 
 
struct point
{
    float x, y;
}p[NMAX];
 
int N;
 
float absN (float x)
{
    if ( x < 0 )
        return -x;
    else
        return x;
}
 
int compare ( point a, point b )
{
    if (absN (a.x - b.x) < ERROR)
        return a.y < b.y;
    return a.x < b.x;
}
 
int binSearch(int li, int ls, point val)
{
    int m = ( li + ls ) / 2;
    if ( absN (p[m].x - val.x) < ERROR && absN (p[m].y - val.y) < ERROR )
    {
        return 1;
    }
    else
    {
        if (li <= ls)
        {
            if ( compare(p[m], val) )
                binSearch (m + 1, ls, val);
            else
                binSearch (li, m-1, val);
                 
        }
        else
            return -1;
    }
}
 
int main()
{
 
    FILE *f = fopen ("patrate3.in", "r");
    FILE *g = fopen ("patrate3.out", "w");
 
    fscanf (f, "%d", &N);
    for (int i = 0 ; i < N; i++)
    {
        fscanf (f, "%f %f", &p[i].x, &p[i].y);
    }
 
    //qsort (p, N, sizeof(point), compare);
    sort(p, p + N, compare); 
     
    point A, B;
     
    int nrSquare = 0;
     
    for (int i = 0; i < N - 1; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            float mijx = ( p[i].x + p[j].x ) / 2;
            float mijy = ( p[i].y + p[j].y ) / 2;
            float dx = absN ( mijx - p[i].x );
            float dy = absN ( mijy - p[i].y ); 
            if ( p[i].y < p[j].y )
            {
                A.x = mijx + dy;
                A.y = mijy - dx;
                B.x = mijx - dy;
                B.y = mijy + dx;
                 
                if ( binSearch (0, N-1, A) > 0 && binSearch (0, N-1, B) > 0 )
                    nrSquare++;
            }
            else
            {
                A.x = mijx - dy;
                A.y = mijy - dx;
                B.x = mijx + dy;
                B.y = mijy + dx;
 
                if ( binSearch (0, N-1, A) > 0 && binSearch (0, N-1, B) > 0 )
                    nrSquare++;
            }
        }
    }
    fprintf(g, "%d", nrSquare / 2);
    fclose(f); fclose(g);
    return 0;
}