Cod sursa(job #2613896)

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

#define er 0.000001
#define x first
#define y second

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].x>>pct[i].y;
}

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

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

        if(abs(pct[mij].x-x)<=er && abs(pct[mij].y-y)<=er)
            return mij;
        if(x-pct[mij].x>=er)
            st=mij+1;
        else
        {
            if(abs(pct[mij].x-x)<=er && y-pct[mij].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 x2,y2,x3,y3;

            double mijX=(pct[i].x+pct[j].x)/2.0,
                   mijY=(pct[i].y+pct[j].y)/2.0;

            double dx=abs(pct[i].x-mijX),dy=abs(pct[i].y-mijY);

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

            if(pct[i].y<pct[j].y)
            {
                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;
}