Cod sursa(job #2314843)

Utilizator IordachescuAncaFMI Iordachescu Anca Mihaela IordachescuAnca Data 9 ianuarie 2019 03:50:53
Problema Patrate 3 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.02 kb
#include<fstream>
#include<algorithm>
#include<cmath>
#define e 0.0001
using namespace std;
ifstream fin("patrate3.in");
ofstream fout("patrate3.out");

struct punct
{
    double x,y;
};
punct v[1010];
int n,i,j,x0,dx,dy;
bool compar(punct a, punct b)
{
    if(fabs(a.x-b.x)>=e)
        {
            if(a.x<b.x)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }
    if(a.y<b.y)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}


int cautare(punct a)
{
    int st=1;
    int dr=n;

    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(fabs(a.x-v[mij].x)<e&&fabs(a.y-v[mij].y)<e)
        {
            return 1;
        }
        else
        {
            if(st>dr)
            {
                return 0;
            }
            else
            {
                if(compar(a,v[mij])==1)
                {
                    dr=mij-1;
                }
                else
                {
                    st=mij+1;
                }
            }
        }
    }
}

int main()
{

    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>v[i].x>>v[i].y;
    }

    sort(v+1, v+n+1, compar);
    int ans=0;
    for(i=1;i<=n;i++)
        for(j=i+1;j<= n;j++)
        {
            punct c;
            c.y=(v[i].x+v[j].x)/2;
            c.y=(v[i].y+v[j].y)/2;

            dx=fabs(c.x-v[i].x);
            dy=fabs(c.y-v[i].y);
            punct x1,x2;
            if(v[i].y<v[j].y)
            {
                x1.x=c.x+dy;
                x1.y=c.y-dx;

                x2.x=c.x-dy;
                x2.y=c.y+dx;
            }
            else
            {
                x1.x=c.x-dy;
                x1.y=c.y-dx;

                x2.x=c.x+dy;
                x2.y=c.y+dx;
            }

            if(cautare(x1)==1&&cautare(x2)==1)
            {
                ans++;
            }
        }

    fout<<ans/2;

    return 0;
}