Cod sursa(job #2625881)

Utilizator RomanacheRoman Alexandru-George Romanache Data 6 iunie 2020 10:38:11
Problema Patrate 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <bits/stdc++.h>

#define N 1010
#define R 0.000001


using namespace std;

fstream f("patrate3.in",ios::in);
fstream g("patrate3.out",ios::out);

struct pct
{
    double x,y;
};

pct v[N];
int n,i,j;

double modul(double x)
{
    if(x<0)
        return -x;
    return x;
}

int CautBin(double x,double y)
{
    int st=1,dr=n,mij;
    while(st<=dr)
    {
        mij=(st+dr)>>1;
        if(modul(x-v[mij].x)<=R && modul(y-v[mij].y)<=R)
            return 1; // Punctul este gasit
        if(x-v[mij].x>=R)
            st=mij+1;
        else
        {
            if(modul(x-v[mij].x)<=R && y-v[mij].y>R)
                st=mij+1;
            else
                dr=mij-1;
        }
    }
    return 0;
}

inline int Comp(pct a,pct b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}

int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i].x>>v[i].y;

    sort(v+1,v+n+1,Comp);
    int rez=0;
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
        {
            double x,y,x2,y2,xm,ym,xd,yd;
            xm=(v[i].x+v[j].x)/2.0;
            ym=(v[i].y+v[j].y)/2.0;
            xd=modul(v[i].x-xm);
            yd=modul(v[i].y-ym);
            if(v[i].y<v[j].y)
            {
                x=xm+yd;
                y=ym-xd;
                x2=xm-yd;
                y2=ym+xd;
            }
            else
            {
                x=xm-yd;
                y=ym-xd;
                x2=xm+yd;
                y2=ym+xd;
            }
            if(CautBin(x,y) && CautBin(x2,y2))
                rez++;
        }
    g<<rez/2;

    return 0;
}