Cod sursa(job #1693513)

Utilizator sucureiSucureiRobert sucurei Data 23 aprilie 2016 11:59:42
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <algorithm>
#include <fstream>

using namespace std;

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

const int nmax = 1000;
const int step_max = 512;

struct str
{
    int x, y;
};
inline str mp(const int &x,const int &y)
{
    str sol;
    sol.x = x; sol.y = y;
    return sol;
}
bool str_cmp_xl(const str &x,const str &y)
{
    if ( x.x != y.x ) return x.x < y.x;
    return x.y < y.y;
}

str v[nmax+1];

int main(  )
{
    int n;
    fin >> n;
    for (int i=1;i<=n;++i)
    {
        string s;
        fin>>s;
        for (int j=0;j<(int)s.size();++j)
            if (s[j]>='0'&& s[j]<='9')
                v[i].x=v[i].x*10+s[j]-'0';
        if (s[0]=='-')
            v[i].x*=-1;
        v[i].x*=2;
        fin>>s;
        for (int j=0;j<(int)s.size();++j)
            if ( s[j] >= '0' && s[j] <= '9' )
                v[i].y = v[i].y*10+s[j]-'0';
        if (s[0]=='-')
            v[i].y *= -1;
        v[i].y *= 2;
    }
    sort(v+1,v+n+1,str_cmp_xl);
    int sol=0;
    for (int i=1;i<n;++i)
    {
        for (int j=i+1;j<=n;++j)
        {
            int c = 0;
            for (int ind=0;ind<2;++ind)
            {
                str aux;
                aux.x=(v[i].x+v[i].y+v[j].x-v[j].y)/2;
                aux.y=(-v[i].x+v[i].y+v[j].x+v[j].y)/2;
                int p=0;
                for (int step=step_max;step>0;step/= 2)
                    if (p+step<=n && str_cmp_xl(v[p+step],aux))
                        p+=step;
                if (p+1<=n && v[p+1].x==aux.x && v[p+1].y==aux.y )
                    ++c;
                int i_aux=i;
                i=j;
                j=i_aux;
            }
            if (c==2)
                ++ sol;
        }
    }
    fout << sol/2 << "\n";
    return 0;
}