Cod sursa(job #476353)

Utilizator freak93Adrian Budau freak93 Data 10 august 2010 19:36:41
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<fstream>
#include<algorithm>

using namespace std;

const char iname[]="patrate3.in";
const char oname[]="patrate3.out";
const int maxn=1005;

ifstream f(iname);
ofstream g(oname);

double eps=1e-4;
int cmp(double a,double b)
{
    if(a+eps<b)
        return -1;
    if(b+eps<a)
        return 1;
    return 0;
}

class point
{
    public:
    double x,y;
    point():x(0),y(0){}
    point(double _x,double _y):x(_x),y(_y){}
    bool operator<(point v) const
    {
        int a=cmp(x,v.x);
        if(a==0)
            return cmp(y,v.y)==-1;
        return a==-1;
    }
    bool operator==(point v) const
    {
        return cmp(x,v.x)==0&&cmp(y,v.y)==0;
    }
    point rot_right(point a) const
    {
        return point(a.y-y+a.x,x-a.x+a.y);
    }
    point rot_left(point a) const
    {
        return point(y-a.y+a.x,a.x-x+a.y);
    }
    friend ifstream& operator>>(ifstream &f,point &x)
    {
        f>>x.x>>x.y;
        return f;
    }
} a[maxn],il,ir,jl,jr;

int i,j,n,rez;

inline bool find(point x)
{
    int step,i;
    for(step=1;step<n;step<<=1);
    for(i=0;step;step>>=1)
        if(i+step<n&&a[i+step-1]<x)
            i+=step;
    if(i==n)
        return false;
    return a[i]==x;
}

int main()
{
    f>>n;
    for(i=0;i<n;++i)
        f>>a[i];
    sort(a,a+n);
    for(i=0;i<n;++i)
        for(j=i+1;j<n;++j)
        {
            ir=a[i].rot_right(a[j]);il=a[i].rot_left(a[j]);
            jr=a[j].rot_right(a[i]);jl=a[j].rot_left(a[i]);


            rez+=(find(a[i].rot_right(a[j]))==1&&find(a[j].rot_left(a[i])));
            rez+=(find(a[j].rot_right(a[i]))==1&&find(a[i].rot_left(a[j])));
        }

    g<<(rez/4)<<"\n";
}