Cod sursa(job #1051183)

Utilizator stefyvoltFMI Stefan Niculae stefyvolt Data 9 decembrie 2013 19:52:04
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.09 kb
#include <iostream>
#include <fstream>

using namespace std;

#define dim 9973                        // 1543 pt 1k; 9973 pt 10k

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

int n, k, v[1001];

struct intrare
{
    float x, y;
    intrare *urm;
} *Hash[dim+1];                           // vectorul de liste de coordonate

int h(float x, float y)
{
    float z = (x+y) *100;
    if(z<0) z *= -1;
    return ((int)z) % dim;              // h(x,y) returneaza (modulul sumei cu virgula deplasata de 2 ori spre dreapta) mod dim
}

void adaugare(float x, float y, int i)
{
    int indice = h(x,y);                // indicele va fi h(x,y)
    v[i] = indice;                      // in v retinem unde avem puse date, pt o parcurgere mai rapida (maxim 1001 vs mereu 1543)

    intrare *noua = new intrare;        // creeam o noua intrare cu indicii x, y si urm NULL
    noua->urm = NULL;
    noua->x = x;
    noua->y = y;

    if(!Hash[indice])                   // o adaugam in hash pe pozitia indice
        Hash[indice] = noua;
    else                                // la sfarsitul listei, daca aceasta nu este vida
    {
        intrare *c;
        for(c = Hash[indice+1]; c->urm; c=c->urm);
        c->urm = noua;
    }
}

void citire()
{
    float x, y;

    f >> n;
    for(int i=1; i<=n; i++)
    {
        f >> x >> y;
        adaugare(x,y,i);                 // adaugam in hash
    }
}

void afisare()
{
    cout << endl;
    cout << endl;
    cout << endl;

    for(int i=0; i<dim; i++)            // parcurgem vectorul
        if(Hash[i])                     // si afisam elem din vector (liste de coord)
        {
            cout << endl << i << ": ";
            for(intrare *c = Hash[i]; c; c=c->urm)
                cout << c->x << ' ' << c->y << ", ";
        }
    cout << endl;
    cout << endl;
    cout << endl;
    cout << endl;
}

bool egale(float a, float b)
{
    float c = a-b;
    if(c<0) c *= -1;

    return (c<=0.00001);
}

bool cauta(float x, float y)
{
    int indice = h(x,y);

    for(intrare *c = Hash[indice]; c; c=c->urm)
        if(egale(c->x,x) && egale(c->y,y))
            return 1;
    for(intrare *d = Hash[indice+1]; d; d=d->urm)
        if(egale(d->x,x) && egale(d->y,y))
            return 1;

    return 0;
}

void rezolva()
{
    float x1,y1, x2,y2, x3,y3, x4,y4, a1,b1, a2,b2;

    for(int i=1; i<n; i++)
    {
        x1 = Hash[v[i]]->x; y1 = Hash[v[i]]->y;
        for(int j=i+1; j<=n; j++)
        {
            x2 = Hash[v[j]]->x; y2 = Hash[v[j]]->y;

            a1 = (x1+x2)/2; b1 = (y1+y2)/2;
            a2 = (y1-y2)/2; b2 = (x2-x1)/2;

            x3 = a1+a2; y3 = b1+b2;
            x4 = a1-a2; y4 = b1-b2;

            if(cauta(x3,y3) && cauta(x4,y4))
            {
                //cout << "pt (" << x1 << ',' << y1 << ") si (" << x2 << ',' << y2 << ") avem: 1(" << a1 << ',' << b1 << "), 2(" << a2 << ',' << b2 << "), 3(" << x3 << ',' << y3 << ")"<<h(x3,y3) <<" 4(" << x4 << ','<< y4 << ')' << h(x4,y4) << endl;
                k++;
            }
        }
    }
}

int main()
{
    citire();
    //afisare();
    rezolva();

    //cout << (float)k/2;
    g << k;

    return 0;
}