Cod sursa(job #1321105)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 18 ianuarie 2015 19:34:05
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 2.58 kb
#include<stdio.h>
#include<math.h>
#define eps 0.001
struct point
{
    double x,y;
};
int n;
int f[1002];
point v[1002];

void read()
{
    freopen("patrate3.in","r",stdin);
    freopen("patrate3.out","w",stdout);
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++)
        scanf("%lf%lf",&v[i].x,&v[i].y);
}

int part(int st, int dr)
{
    int i,j,m;
    point aux,p;
    m=(st+dr)>>1;
    p=v[m];
    i=st-1;
    j=dr+1;
    while(1)
    {
        do{++i;}while((p.x-v[i].x)>=eps || ((fabs(p.x-v[i].x)<eps) && (p.y-v[i].y>=eps)));
        do{--j;}while((v[j].x-p.x)>=eps || ((fabs(p.x-v[j].x)<eps) && (v[j].y-p.y>=eps)));
        if(i<j)
        {
            aux=v[i];
            v[i]=v[j];
            v[j]=aux;
        }
        else
            return j;
    }
}

void quick(int st, int dr)
{
    int p;
    if(st<dr)
    {
        p=part(st,dr);
        quick(st,p);
        quick(p+1,dr);
    }
}

int cautare(point x)
{
    int st,dr,m;
    st=1;
    dr=n;
    while(st!=dr)
    {
        m=(st+dr)>>1;
        if(((v[m].x-x.x)>=eps) || ((fabs(v[m].x-x.x)<eps) && (v[m].y-x.y)>=eps))
            dr=m;
        else
            st=m+1;
    }
    return st-1;
}

void rez()
{
    int i,j,patrate=0,poz1,poz2;
    point m,p2,p3,d;
    for(i=1;i<n;i++)
        for(j=i+1;j<=n;j++)
        {
            m.x=(v[i].x+v[j].x)*0.5;
            m.y=(v[i].y+v[j].y)*0.5;
            d.x=fabs(m.x-v[i].x);
            d.y=fabs(m.y-v[i].y);
            if((v[j].y-v[i].y)>=eps)
            {
                p2.x=m.x+d.y;
                p2.y=m.y-d.x;
                p3.x=m.x-d.y;
                p3.y=m.y+d.x;
            }
            else
            {
                //x2 = mijx - dy, y2 = mijy - dx, x3 = mijx + dy iar y3 = mijy + dx.
                p2.x=m.x-d.y;
                p2.y=m.y-d.x;
                p3.x=m.x+d.y;
                p3.y=m.y+d.x;
            }
            poz1=cautare(p2);
            poz2=cautare(p3);
            if((fabs(v[poz1].x-p2.x)<eps) && (fabs(v[poz1].y-p2.y)<eps))
                if((fabs(v[poz2].x-p3.x)<eps) && (fabs(v[poz2].y-p3.y)<eps))
                    if(cautare(p2) && cautare(p3))
                    {
                        if(f[i]==0 && f[j]==0 && f[poz1]==0 && f[poz2]==0)
                        {
                            patrate++;
                            f[i]=f[j]=f[poz1]=f[poz2]=1;
                        }
                    }
        }
        printf("%d\n",patrate);
}

int main()
{
    read();
    quick(1,n);
    rez();
    return 0;
}