Cod sursa(job #1065502)

Utilizator mariacMaria Constantin mariac Data 23 decembrie 2013 13:50:51
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.73 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("patrate3.in");
ofstream fout("patrate3.out");

struct punct
{
    double x, y;
};
vector<punct> v;
int N, nr_p;
bool cmp(punct a, punct b)
{
    if(a.x  < b.x)return 1;
    if(a.x == b.x)return a.y < b.y;
    return 0;
}
double abs(double x)
{
    double munu  = -1;
    if(x > 0) return x;
    return munu * x;
}
bool cauta(punct c)
{
    int i, step;
    for (step = 1; step < N; step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < N && (( v[i + step].x - c.x) < 0.0001 || abs(v[i + step].x - c.x) <= 0.0001 && v[i + step].y - c.y <= 0.0001))
           i += step;
    if( abs(v[i].x - c.x) <= 0.0001 && abs(v[i].y - c.y) <= 0.0001) return 1;
    return 0;
}

int main()
{
    int i, j;
    fin >> N;
    for( i = 1; i <= N; i++ )
    {
        punct aux;
        fin >> aux.x >> aux.y;
        v.push_back(aux);
    }
    sort(v.begin(), v.end(), cmp);
    for( i = 0; i < N - 1; i++)
        for( j = i + 1; j < N; j++)
    {
        punct mij, d, a, b;
        mij.x = (v[i].x + v[j].x) / 2;
        mij.y = (v[i].y + v[j].y) / 2;
        d.x = abs(mij.x - v[i].x);
        d.y = abs(mij.y - v[i].y);
        if(v[i].y < v[j].y)
        {
             a.x = mij.x + d.y;
             a.y = mij.y - d.x;
             b.x = mij.x - d.y;
             b.y = mij.y + d.x;
        }
        else
        {
             a.x = mij.x - d.y;
             a.y = mij.y - d.x;
             b.x = mij.x + d.y;
             b.y = mij.y + d.x;
        }
        int ok = 0;
        ok += cauta(a);
        if(ok) ok += cauta(b);
        if(ok == 2)nr_p++;
    }
    fout<<nr_p / 2;
    return 0;
}