Cod sursa(job #1404829)

Utilizator raduzxstefanescu radu raduzx Data 28 martie 2015 16:26:19
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#define e 0.00001
using namespace std;
typedef double var;
struct axe
{
    var  x;
    var y;
};
axe a[1001];
int MAX,n;
bool cmp(axe q,axe w)
{
    if(q.x<w.x)
        return true;
    if(q.x==w.x)
        if(q.y<w.y)
            return true;
        else
            return false;
    return false;
}

int cautbin(var b,var c)
{
    int poz1=0,poz2=0,i,poz3;
    for(i=MAX/2;i;i/=2)
    {
        if(poz1+i<=n and a[poz1+i].x<b)
            poz1+=i;
    }
    for(i=MAX/2;i;i/=2)
    {
        if(poz2+i<=n and a[poz2+i].x<=b)
            poz2+=i;
    }
    if(b-a[poz1+1].x<=e)
    {
        int MAX1=0;
        for(MAX1=1;MAX1<=poz2-poz1+1;MAX1*=2);
        int poz2=0;
        for(i=MAX1/2;i;i/=2)
        {
            if(poz2+i<poz2-poz1+1 and a[poz2+i].y<c)
                poz2+=i;
        }
        if(c-a[poz2+1].y<=e) return 1;
    }
    return 0;


}


int main()
{
    ifstream f("patrate3.in");
    ofstream g("patrate3.out");
    int i,j,nr=0;
    f>>n;
    for(MAX=1;MAX<=n;MAX*=2);
    for(i=1;i<=n;i++)
        f>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);

    for(i=1;i<=n;i++)
    {
        for(j=i+1;j<=n;j++)
        {
          var mijx=(a[i].x+a[j].x)/2.0;
          var mijy=(a[i].y+a[j].y)/2.0;
          var dx = fabs(mijx - a[i].x);
          var dy = fabs(mijy - a[i].y);
          if(a[i].y < a[j].y){
                var x2 = mijx + dy;
                var y2 = mijy - dx;
                var x3 = mijx - dy;
                var y3 = mijy + dx;
                if(cautbin(x2,y2)==1)
                    if(cautbin(x3,y3)==1)
                        {nr+=1;}
          }
          else{
            var x2 = mijx - dy;
            var y2 = mijy - dx;
            var x3 = mijx + dy;
            var y3 = mijy + dx;
            if(cautbin(x2,y2)==1)
                if(cautbin(x3,y3)==1)
                    {nr+=1;}
          }
        }
    }
    g<<nr;
    f.close();
    g.close();
    return 0;
}