Cod sursa(job #2626063)

Utilizator UrsaWarlordFrincu Madalin Gabriel UrsaWarlord Data 6 iunie 2020 11:41:07
Problema Patrate 3 Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <bits/stdc++.h>
using namespace std;

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

int N,i,j;

struct punct
{
    double x,y;
    bool operator<(const punct &a) const
    {
        if(abs(x-a.x) < 0.0001)
            return y < a.y;
        return x < a.x;
    }
};

punct puncte[1001];

bool cautare_binara(punct a)
{
    double x = a.x;
    double y= a.y;
    cout << x << " " << y << endl;
    int st=1, dr=N, mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(abs(x-puncte[mij].x) <= 0.0001 && abs(y-puncte[mij].y) <= 0.0001 )
            return true;
        if(puncte[mij] < a)
            st = mij+1;
        else
            dr = mij-1;
    }
    return false;
}


int main()
{
    int nr =0;
    f>>N;
    for(i=1;i<=N;i++){
        f>>puncte[i].x >> puncte[i].y;
    }
    sort(puncte+1,puncte+1+N);
    for(i=1;i<=N;i++)
        cout << puncte[i].x << " " << puncte[i].y << endl;
    cout << endl;
    for(i=1;i<=N-1;i++)
        for(j=i+1;j<=N;j++)
    {
        punct a,b, mij, delta;

        mij.x = (puncte[i].x + puncte[j].x) / 2;
        mij.y = (puncte[i].y + puncte[j].y) / 2;
        delta.x = abs(puncte[i].x - mij.x);
        delta.y = abs(puncte[i].y - mij.y);
        if(puncte[i].y < puncte[j].y)
        {
            a.x = mij.x + delta.y;
            a.y = mij.y - delta.x;
            b.x = mij.x - delta.y;
            b.y = mij.y + delta.x;
        }
        else
        {
            a.x = mij.x - delta.y;
            a.y = mij.y - delta.x;
            b.x = mij.x + delta.y;
            b.y = mij.y + delta.x;
        }

        if(cautare_binara(a) && cautare_binara(b))
            nr++;
    }
    g<<nr/2;
    f.close();
    g.close();

}