Cod sursa(job #2614991)

Utilizator VladAlexandruAnghelache Vlad VladAlexandru Data 13 mai 2020 01:09:37
Problema Patrate 3 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <iostream>
#include<fstream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>

using namespace std;
ifstream fin("patrate3.in");
ofstream fout("patrate3.out");

struct punct
{
    double x,y;
};
punct p;
double dist(punct a, punct b)
{
    double d=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    return d;
}
bool myfunction(punct a, punct b)
{
    double d1=dist(p,a);
    double d2=dist(p,b);
    return (d1<d2);
}


int caut_bin(int st,int sf,vector<punct> v,double x)
{
    if(st>sf)
        return -1;
    int m=(st+sf)/2;
    if(dist(p,v[m])==x)
        return m;
    if(dist(p,v[m])<x)
        return caut_bin(m+1,sf,v,x);
    if(dist(p,v[m])>x)
        return caut_bin(st,m-1,v,x);
}

int main()
{
    int n;
    int nr=0;
    vector<punct> v;
    //vector<int> abs;
    //vector<int> ord;
    fin>>n;
    for(int i=0; i<n; i++)
    {
        double x,y;
        fin>>x>>y;
        p.x=x;
        p.y=y;
        //cout<<x<<" "<<y<<"\n";
        //abs.push_back(p.x);
        //ord.push_back(p.y);
        if(i>=3)
        {
            //cout<<"ok1\n";
            sort(v.begin(),v.end(),myfunction);
            for(int j=1; j<v.size(); j++)
            {
                //cout<<"ok2\n";
                double d1=dist(p,v[j-1]);
                double d2=dist(p,v[j]);
                int ok=j;
                while(ok<v.size()&&d1==d2)
                {
                    //cout<<"ok3\n";
                    double d3=dist(v[j-1],v[ok]);
                    int b=caut_bin(0,v.size(),v,d3);
                    if(b!=-1&&dist(v[j-1],v[b])==d2&&dist(v[ok],v[b])==d2)
                        nr++;
                    ok++;
                    d2=dist(p,v[ok]);
                }
            }
        }
        v.push_back(p);
    }
    fout<<nr;

    return 0;
}