Cod sursa(job #1083556)

Utilizator leontinLeontin leontin Data 16 ianuarie 2014 03:35:46
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <fstream>
#include <iostream>
#include <math.h>
#include <queue>
#include <algorithm>

using namespace std;

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

int n, i, j, nr=0;
double  a, b, dx, dy;

typedef struct punct{double x; double y;};
punct v[1005], aux, m, p1, p2;

bool compare(punct a, punct b)
{
    if ( fabs(a.x-b.x) >= 0.0001 )
        return (a.x<b.x);
    return (a.y<b.y);
}


bool Bynary(punct p, int l, int r)
{
    int m = (l+r)/2;


    if( fabs(p.x-v[m].x) < 0.0001 && fabs(p.y-v[m].y) < 0.0001 )
        return true;
    else
        if(l>r)
            return false;
        else
            if(compare(p, v[m]))
                Bynary(p, l, m-1);
            else
                Bynary(p, m+1, r);
}

int main()
{

    double a, b;
    ifstream fin("patrate3.in");
    ofstream fout("patrate3.out");

    fin>>n;

    for(i = 1; i<=n; i++ )
    {
        fin>>v[i].x>>v[i].y;
    }

    sort(v+1, v+n+1, compare);

    for( i = 1; i <= n; i++ )
        for( j = i+1; j <= n; j++ )
        {
            m.x = (v[i].x + v[j].x)/2;
            m.y = (v[i].y + v[j].y)/2;

            dx = fabs(m.x - v[i].x);
            dy = fabs(m.y - v[i].y);

            if(v[i].y < v[j].y){
                p1.x = m.x + dy;
                p1.y = m.y - dx;

                p2.x = m.x - dy;
                p2.y = m.y + dx;
            }
            else {
                p1.x = m.x - dy;
                p1.y = m.y - dx;

                p2.x = m.x + dy;
                p2.y = m.y + dx;
            }

            if(Bynary(p1, 1, n) && Bynary(p2, 1, n))
                nr++;
        }

    fout<<nr/2;

    return 0;
}