Cod sursa(job #2657554)

Utilizator AswVwsACamburu Luca AswVwsA Data 10 octombrie 2020 23:55:15
Problema Patrate 3 Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.44 kb
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;/*
ifstream cin("ciorna.in");
ofstream cout("ciorna.out");*/
ifstream cin("patrate3.in");
ofstream cout("patrate3.out");
int n;
struct coord
{
    int  x,y;
} v[1004];
int bsright(int  val)
{
    int st=1,dr=n,last=-1;
    while (st<=dr)
    {
        int med=((st+dr)>>1);
        if (v[med].x>val)
            dr=med-1;
        else
        {
            st=med+1;
            if (v[med].x==val)
                last=med;
        }
    }
    return last;

}
int bsleft(int  val)
{
    int st=1,dr=n,last=-1;
    while (st<=dr)
    {
        int med=((st+dr)>>1);
        if (v[med].x<val)
            st=med+1;
        else
        {
            dr=med-1;
            if (v[med].x==val)
                last=med;
        }
    }
    return last;
}

bool cmp(coord a, coord b)
{
    return a.x<b.x;
}

int main()
{

    /*
    91000 265100
    359300 348700
    266950 172750
    183350 441050
    */

    cin>>n;
    cin.get();
    for (int i=1; i<=n; ++i)
        {
            char s[30];
            cin.getline(s,sizeof(s));
            char *p=strtok(s," ");
            for (;*p;++p)
                if (*p!='.')v[i].x=v[i].x*10+*p-'0';
            p=strtok(0," ");
            for (;*p;++p)
                if (*p!='.')v[i].y=v[i].y*10+*p-'0';
            }
    sort(v+1,v+n+1,cmp);
    //for (int i=1;i<=n;++i)
    //cout<<v[i].x<<' '<<v[i].y<<'\n';
    unsigned long long  cnt=0;
    for (int i=1; i<n; ++i)
        for (int j=i+1; j<=n; ++j)
        {

            int wanted1,wanted2;
            wanted1=v[i].y-v[j].y+v[j].x;// x c
            wanted2=v[j].x-v[i].x+v[j].y;// y c
            int bl,br;
            bl=bsleft(wanted1);
            br=bsright(wanted1);
            if(bl!=-1 and br!=-1
              )
            {
                for (int l=bl; l<=br; ++l)
                    if (v[l].y==wanted2)
                        if (
                            (v[i].x-v[j].x)*(v[i].x-v[j].x)+
                            (v[i].y-v[j].y)*(v[i].y-v[j].y)+
                            (v[j].x-v[l].x)*(v[j].x-v[l].x)+
                            (v[j].y-v[l].y)*(v[j].y-v[l].y)==
                            (v[i].x-v[l].x)*(v[i].x-v[l].x)+
                            (v[i].y-v[l].y)*(v[i].y-v[l].y)
                            )
                        {
                            int a1,b1;
                            //cout<<"i'm here.";
                            wanted1=v[i].y-v[j].y+v[i].x;//x d
                            wanted2=v[j].x-v[i].x+v[i].y;// y d
                            int lef=bsleft(wanted1),
                            righ =bsright(wanted1);
                            if(lef!=-1 and righ!=-1
                              )
                            {
                                for (int l1=lef; l1<=righ; ++l1)
                                    if(wanted2==v[l1].y){
                                        cnt++;

                                        /*cout<<v[i].x<<' '<<v[i].y<<'\n'
                                        <<v[j].x<<' '<<v[j].y<<'\n'<<
                                        v[l].x<<' '<<v[l].y<<'\n'<<
                                        v[l1].x<<' '<<v[l1].y<<"\n\n";*/
                                    }
                            }
                        }
            }
        }
    cout<<(cnt>>1);
}