Cod sursa(job #20704)

Utilizator mariusdrgdragus marius mariusdrg Data 21 februarie 2007 22:14:23
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.35 kb
#include<stdio.h>
#include<algorithm>
#define lf double
#define eps 0.00001

using namespace std;


const int maxn = 1001;

lf x[maxn];
lf y[maxn];
int j;
lf pctx1;
lf pctx2;
lf pcty1;
lf pcty2;
int sol;
int i;
int n;
int a[maxn];


void patrat(lf x,lf y,lf x1,lf y1, lf &r1,lf &r2,lf &r3,lf &r4)
{
        r1=x+y1-y;
        r2=y+x-x1;
        r3=x1+y1-y;
        r4=y1+x-x1;
}

lf modul(lf a)
{
        if (a<0)
        {
                return (-1)*a;
        }
        return a;

}

int eps1(lf a,lf b)
{
        if (modul(a-b)<eps) return 1;
        return 0;
}

int bs(lf val1,lf val2)
{
        int x2 = 0, p = 1 ;
        
        for(p=1;p<=n;p<<=1)
        {

        }

        for(;p;p>>=1)
        {
                if(x2+p>n) continue;
                if (x[a[x2+p]]<val1&&!eps1(x[a[x2+p]],val1))
                {
                        x2+=p;
                        continue;
                }
                if (eps1(x[a[x2+p]],val1))
                {
                        if (!eps1(y[a[x2+p]],val2)&&y[a[x2+p]]<val2)
                        {
                                x2+=p;
                                continue;
                        }
                        if (eps1(y[a[x2+p]],val2))
                        {
                                x2+=p;
                                continue;
                        }
                }
        }
        if (eps1(x[a[x2]],val1)&& eps1(y[a[x2]],val2)) return 1;
        return 0;
}



bool cmpf(const int &a,const int &b)
{
        if (x[a]!=x[b])return x[a]<x[b];
        return y[a]<y[b];
}

int main()
{
        freopen("patrate3.in","r",stdin);
        freopen("patrate3.out","w",stdout);
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
                scanf("%lf %lf",&x[i],&y[i]);
                a[i]=i;
        }
        sort(a+1,a+n+1,cmpf);
        int sol = 0;
        for(i=1;i<=n;i++)
                for(j=i+1;j<=n;j++)

                {
                        if (i==j) continue;
                        patrat(x[a[i]],y[a[i]],x[a[j]],y[a[j]],pctx1,pcty1,pctx2,pcty2);
                        if (bs(pctx1,pcty1))
                        {
                                if (bs(pctx2,pcty2))
                                {
                       //                                    printf("%.5lf %.5lf %lf.5 %lf.5 %.5lf %.5lf %.5lf %.5lf\n",x[a[i]],y[a[i]],x[a[j]],y[a[j]],pctx1,pcty1,pctx2,pcty2);
                     
                                        sol+=1;
                                }
                        }
                        pctx1=x[a[i]]-(pctx1-x[a[i]]);
                        pcty1=y[a[i]]-(pcty1-y[a[i]]);
                        pctx2=x[a[j]]-(pctx2-x[a[j]]);
                        pcty2=y[a[j]]-(pcty2-y[a[j]]);
                        if (bs(pctx1,pcty1))
                        {
                                  if (bs(pctx2,pcty2))
                                  {
                     //                   printf("%.5lf %.5lf %lf.5 %lf.5 %.5lf %.5lf %.5lf %.5lf\n",x[a[i]],y[a[i]],x[a[j]],y[a[j]],pctx1,pcty1,pctx2,pcty2);
                     
                                        sol+=1;
                                  }
                        }
                }
        printf("%d",sol/4);
        return 0;
}