Cod sursa(job #2613889)

Utilizator As932Stanciu Andreea As932 Data 10 mai 2020 20:17:15
Problema Patrate 3 Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>

#define er 0.000001

using namespace std;

ifstream cin("patrate3.in");
ofstream cout("patrate3.out");

int n;
vector < pair <double,double> >pct;

void read()
{
    cin>>n;

    pct.resize(n);

    for(int i=0;i<n;i++)
        cin>>pct[i].first>>pct[i].second;
}

int bin(double x,double y)
{
    int st=0,dr=n-1;

    while(st<=dr)
    {
        int mij=(st+dr)/2;

        if(abs(pct[mij].first-x)<=er && abs(pct[mij].second-y)<=er)
            return mij;
        if(x-pct[mij].first>=er)
            st=mij+1;
        else
        {
            if(abs(pct[mij].first-x)<=er && abs(pct[mij].second-y)>er)
                st=mij+1;
            else
                dr=mij-1;
        }
    }
    return -1;
}

void solve()
{
    int ans=0;

    for(int i=0;i<n-1;i++)
        for(int j=i+1;j<n;j++)
        {
            double x0=pct[i].first,y0=pct[i].second;
            double x1=pct[j].first,y1=pct[j].second;
            double x2,y2,x3,y3;

            double mijX=(x0+x1)/2.0,mijY=(y0+y1)/2.0;
            double dx=abs(x0-mijX),dy=abs(y0-mijY);

            //cout<<mijX<<" "<<mijY<<" "<<dx<<" "<<dy<<"\n";

            if(y0<y1)
            {
                x2=mijX+dy;
                y2=mijY-dx;
                x3=mijX-dy;
                y3=mijY+dx;
            }
            else
            {
                x2=mijX-dy;
                y2=mijY-dx;
                x3=mijX+dy;
                y3=mijY+dx;
            }

            int p1=bin(x2,y2);
            int p2=bin(x3,y3);

            if(p1!=-1 && p2!=-1)
                ans++;
        }

    cout<<ans/2;
}

int main()
{
    read();

    sort(pct.begin(),pct.end());

    solve();

    return 0;
}