Cod sursa(job #2484449)

Utilizator altcontnoualt cont altcontnou Data 31 octombrie 2019 09:34:11
Problema Patrate 3 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

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

float eps=0.0001;

struct p{
    float x, y;

    bool operator==(p alt)
    {
        if (max(x,alt.x)-min(x,alt.x)<=eps && max(y,alt.y)-min(y,alt.y)<=eps)
            return 1;
        return 0;
    }


}puncte[1005], A, B, C, D, mij;

class cmp{
public:
    bool operator()(p a, p b)
    {
        if (a.x==b.x)
            return a.y<b.y;
        return a.x<b.x;
    }
};

int n;

bool cautare_bin(int st, int dr, p punct)
{
    int mij;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (puncte[mij]==punct)
            return 1;
        if (punct.x==puncte[mij].x)
        {
            if (punct.y<puncte[mij].y)
                dr=mij-1;
            else
                st=mij+1;
        }
        else
        {
            if (punct.x<puncte[mij].x)
                dr=mij-1;
            else
                st=mij+1;
        }
    }
    return 0;
}

void solve()
{
    int nr=0;
    float difx, dify;
    for (int i=1; i<n; ++i)
    {
        for (int j=i+1; j<=n; ++j)
        {
            A=puncte[i];
            C=puncte[j];

            mij.x=(A.x+C.x)/2;
            mij.y=(A.y+C.y)/2;

            difx=abs(mij.x-A.x);
            dify=abs(mij.y-A.y);

            if (A.y<C.y)
            {
                B.x=mij.x+dify;
                B.y=mij.y-difx;

                D.x=mij.x-dify;
                D.y=mij.y+difx;
            }
            else
            {
                B.x=mij.x-dify;
                B.y=mij.y-difx;

                D.x=mij.x+dify;
                D.y=mij.y+difx;
            }

            if (cautare_bin(1,n,B) && cautare_bin(1,n,D))
                ++nr;
        }
    }
    g << nr/2;
}

int main()
{
    f >> n;
    for (int i=1; i<=n; ++i)
    {
        f >> puncte[i].x >> puncte[i].y;
    }
    sort(puncte+1, puncte+n+1, cmp());
    solve();

    A.x=puncte[1].x;
    A.y=puncte[1].y;
    return 0;
}