Cod sursa(job #2822535)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 24 decembrie 2021 09:37:31
Problema Patrate 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <fstream>
#include <cmath>

using namespace std;

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

const int maxN = 1005;
int n, npow = 1, ans;
struct coord {
    int x, y;
}v[maxN], h[maxN];

void mergesort(int st, int dr)
{
    if(st == dr)
        return;
    int med = (st + dr) / 2;
    mergesort(st, med);
    mergesort(med + 1, dr);
    int i = st, j = med + 1, k = st;
    while(i <= med || j <= dr)
    {
        if(j > dr || (i <= med && (v[i].x < v[j].x || (v[i].x == v[j].x && v[i].y < v[j].y))))
            h[k++] = v[i++];
        else
            h[k++] = v[j++];
    }
    for(int i = st; i <= dr; i++)
        v[i] = h[i];
}

bool exista(coord pct)
{
    int poz = 0;
    for(int i = npow; i > 0; i = (i >> 1))
    {
        if((poz + i <= n) && (v[poz + i].x < pct.x || (v[poz + i].x == pct.x && v[poz + i].y < pct.y)))
            poz = poz + i;
    }
    if(v[poz + 1].x == pct.x && v[poz + 1].y == pct.y)
        return 1;
    return 0;
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
    {
        double a, b;
        fin >> a >> b;
        a = round (a * 20000);
        b = round (b * 20000);
        v[i].x = a;
        v[i].y = b;
    }
    while(npow * 2 <= n)
        npow = npow * 2;
    mergesort(1, n);
    for(int i = 1; i < n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            coord a, b, mij;
            mij.x = (v[i].x + v[j].x) / 2;
            mij.y = (v[i].y + v[j].y) / 2;
            a.x = mij.x - (v[j].y - mij.y);
            a.y = mij.y + (v[j].x - mij.x);
            b.x = mij.x + (v[j].y - mij.y);
            b.y = mij.y - (v[j].x - mij.x);
            // fout << v[i].x << ' ' << v[i].y << "   " << v[j].x << ' ' << v[j].y << "     " << a.x << ' ' << a.y << "   " << b.x << ' ' << b.y << '\n';
            if(exista(a) && exista(b))
                ans++;
        }
    }
    ans = ans / 2;
    fout << ans;
    return 0;
}