Cod sursa(job #1281984)

Utilizator ChallengeMurtaza Alexandru Challenge Data 3 decembrie 2014 21:16:57
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 2.58 kb
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

const char InFile[]="patrate3.in";
const char OutFile[]="patrate3.out";
const int MaxN=1024;
const double EPS=1e-4;

ifstream fin(InFile);
ofstream fout(OutFile);

inline double myabs(double x)
{
    if(x<0)
    {
        return -x;
    }
    return x;
}

inline bool equal(double x, double y)
{
    return myabs(x-y)<EPS;
}

struct Point
{
    Point(double x=0, double y=0):x(x),y(y){}

    bool operator< (const Point &a)
    {
        if(!equal(x,a.x))
        {
            return x<a.x;
        }
        return y<a.y;
    }

    bool operator== (const Point &a)
    {
        if(!equal(x,a.x))
        {
            return false;
        }
        if(!equal(y,a.y))
        {
            return false;
        }
        return true;
    }

    Point operator+ (const Point &a)
    {
        return Point(x+a.x,y+a.y);
    }

    Point operator* (const double &scalar)
    {
        return Point(x*scalar,y*scalar);
    }

    Point operator- (const Point &a)
    {
        return Point(x-a.x,y-a.y);
    }

    double magnitude()
    {
        return sqrt(x*x+y*y);
    }

    void normalize()
    {
        double d=magnitude();
        x/=d;
        y/=d;
    }

    void rotate90()
    {
        double aux=x;
        x=y;
        y=-aux;
    }

    double x,y;
};

struct Point_cmp
{
    inline bool operator() (const Point &a, const Point &b)
    {
        if(!equal(a.x,b.x))
        {
            return a.x<b.x;
        }
        return a.y<b.y;
    }
};

int N,sol;
Point V[MaxN];

inline bool mysearch(Point P)
{
    int p=1,u=N;
    while(p<=u)
    {
        int m=p+((u-p)>>1);
        if(P==V[m])
        {
            return true;
        }
        if(V[m]<P)
        {
            p=m+1;
        }
        else
        {
            u=m-1;
        }
    }
    return false;
}

inline double dist(const Point &a, const Point &b)
{
    double dx=a.x-b.x;
    double dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}

int main()
{
    fin>>N;
    for(register int i=1;i<=N;++i)
    {
        fin>>V[i].x>>V[i].y;
    }
    fin.close();

    sort(V+1,V+1+N,Point_cmp());

    for(register int i=1;i<=N;++i)
    {
        for(register int j=i+1;j<=N;++j)
        {
            double d=dist(V[i],V[j])*0.5;
            Point M=(V[i]+V[j])*0.5;
            Point N=V[j]-V[i];
            N.normalize();
            N=N*d;
            N.rotate90();
            Point P1=M+N,P2=M-N;

            if(mysearch(P1) && mysearch(P2))
            {
                ++sol;
            }
        }
    }

    fout<<(sol>>1);
    fout.close();
    return 0;
}