Cod sursa(job #2626341)

Utilizator andreea.vasilescuAndreea Vasilescu andreea.vasilescu Data 6 iunie 2020 13:41:52
Problema Patrate 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
ifstream f("patrate3.in");
ofstream g("patrate3.out");
 
const double EPS = 1e-5;
 
struct punct
{
    double x,y;
};
 
int n;
punct p[1001];
 
int egal(double a,double b)
{
    double d=a-b;
    if(d < -EPS)
        return -1;
    if(d > +EPS)
        return +1;
    return 0;
}
 
int egal(const punct &a,const punct &b)
{
    int ex = egal(a.x,b.x);
    int ey = egal(a.y,b.y);
    if(ex==0)
        return ey;
    else
        return ex;
}
 
bool cmp(const punct &a,const punct &b)
{
    return egal(a,b) <0;
}
 
bool cautbin(const punct &a)
{
    int st=1,dr=n;
    while(st<=dr)
    {
        int m=(st+dr)/2;
        int e=egal(p[m],a);
        if(e==0)
            return 1;
        if(e==1)
            dr=m-1;
        else
            st=m+1;
    }
    return 0;
}
 
void solve()
{
    int nrp=0;
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
        {
            punct m,a,b;
            m.x=(p[i].x+p[j].x)/2;
            m.y=(p[i].y+p[j].y)/2;
            a.x= m.x - p[j].y + m.y;
            a.y= m.y + p[j].x - m.x;
            b.x= m.x + p[j].y - m.y;
            b.y= m.y - p[j].x + m.x;
            if(cautbin(a) && cautbin(b))
                nrp++;
        }
    g<<nrp/2;
}
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
        f>>p[i].x>>p[i].y;
    sort(p+1,p+n+1,cmp);
    solve();
    return 0;
}