Cod sursa(job #1053617)

Utilizator LizzardStanbeca Theodor-Ionut Lizzard Data 12 decembrie 2013 21:02:08
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.77 kb
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;

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

struct POINT
{
    float x,y;
};

int e(float , float ),fcmp(POINT , POINT ),cmp(float, float);
bool cb(int , int , POINT , POINT []);

int main(void )
{
    int n,i,j,r=0;
    float mx,my,dx,dy;
    bool ok1,ok2;
    POINT v[1000];
    POINT t1,t2;

    fin>>n;
    for(i=0;i<n;i++)
        fin>>v[i].x>>v[i].y;
    sort(v,v+n,fcmp);

    for(i=0;i<n-1;i++)
        for(j=i+1;j<n;j++)
        {
            mx=(v[i].x+v[j].x)/2.0;
            my=(v[i].y+v[j].y)/2.0;
            dx=fabs(mx-v[i].x);
            dy=fabs(my-v[i].y);

            if(v[i].y<v[j].y)
            {
                t1.x=mx+dy;
                t1.y=my-dx;
                t2.x=mx-dy;
                t2.y=my+dx;
            }
            else
            {
                t1.x=mx-dy;
                t1.y=my-dx;
                t2.x=mx+dy;
                t2.y=my+dx;
            }

            ok1=cb(0,n-1,t1,v);
            if(ok1) ok2=cb(0,n-1,t2,v);

            if(ok1 && ok2)
                r++;
        }
    fout<<r/2;

}

bool cb(int li, int ls, POINT p, POINT v[])
{
    if(li>ls)   return 0;

    int m=(li+ls)/2;
    if(e(v[m].x,p.x) && e(v[m].y,p.y))  return true;
    if(!e(p.x,v[m].x))
    {
        if(p.x<v[m].x)
            return cb(li,m-1,p,v);
        return cb(m+1,ls,p,v);
    }
    else
    {
        if(p.y<v[m].y)
            return cb(li,m-1,p,v);
        return cb(m+1,ls,p,v);
    }
}

int fcmp(POINT a, POINT b)
{
    if(e(a.x,b.x))    return a.y<b.y;
    return a.x<b.x;
}

int e (float a, float b)
{
    if (fabs (a-b)<=0.0001)
        return 1;
    return 0;
}