Cod sursa(job #1447549)

Utilizator Dragne.Andrei11Dragne Andrei Dragne.Andrei11 Data 4 iunie 2015 18:19:11
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 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+e<b)
            poz1+=i;
    }
    for(i=MAX/2;i;i/=2)
    {
        if(poz2+i<=n and a[poz2+i].x+e<=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+e<c)
                poz2+=i;
        }
        if(c-a[poz2+1].y<=e) return 1;
    }
    return 0;


}
int cb(var b,var c)
{
    int st=1,dr=n,mij=0;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (abs(a[mij].x-b)<=e && abs(a[mij].y-c)<=e) return 1;
        if (abs(a[mij].x-b)<=e && a[mij].y<c) st=mij+1;
        else if (abs(a[mij].x-b)<=e) dr=mij-1;
        else if (a[mij].x<b) st=mij+1;
        else dr=mij-1;
    }
    return 0;
}

int main()
{
    freopen("patrate3.in", "r", stdin);
    freopen("patrate3.out", "w", stdout);
    int i,j,nr=0;
    scanf("%d", &n);
    for(MAX=1;MAX<=n;MAX*=2);
    for(i=1;i<=n;i++)
        scanf("%lf%lf", &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(cb(x2,y2)==1)
                    if(cb(x3,y3)==1)
                        {nr+=1;}
          }
          else{
            var x2 = mijx - dy;
            var y2 = mijy - dx;
            var x3 = mijx + dy;
            var y3 = mijy + dx;
            if(cb(x2,y2)==1)
                if(cb(x3,y3)==1)
                    {nr+=1;}
          }
        }
    }
    printf("%d\n", nr/2);
    return 0;
}