Cod sursa(job #315798)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 17 mai 2009 13:11:06
Problema Patrate 3 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include<stdio.h>
#include<stdlib.h>
struct pct{long x,y;}a[1111],a0,a1,a2,a3,mij,d;
long n,i,st,dr,j,gas,m,nr,ax,ay,xx1;
long partit(pct a[ ],long st, long dr)
{long i,j,m;
 pct piv,aa;
 m=(st+dr)/2;
 piv=a[m];
 i=st-1;
 j=dr+1;
 while(1)
  {do{++i;} while(a[i].x<piv.x||(a[i].x==piv.x&&a[i].y<piv.y));
   do{--j;} while(a[j].x>piv.x||(a[j].x==piv.x&&a[j].y>piv.y));
   if (i<j)
	 {aa=a[i];a[i]=a[j];a[j]=aa;}
	   else
	 return j;
  }
}
void quicks(pct a[ ],long st,long dr)
{long p;
 if (st<dr)
   {p=partit(a,st,dr);
	quicks(a,st,p);
	quicks(a,p+1,dr);
   }
}
int main()
{
 freopen("patrate3.in","r",stdin);
 freopen("patrate3.out","w",stdout);
 scanf("%ld",&n);
 for(i=1;i<=n;++i)
    {scanf("%ld.%ld",&ax,&ay);
     a[i].x=ax*100000;
     xx1=1;
     if(ax<0)xx1=-1;
     a[i].x+=((ay*10)*xx1);
     scanf("%ld.%ld",&ax,&ay);
     a[i].y=ax*100000;
     xx1=1;
     if(ax<0)xx1=-1;
     a[i].y+=((ay*10)*xx1);}
 quicks(a,1,n);
 for(i=1;i<=n;++i)
    for(j=i+1;j<=n;++j)
       if((a[i].x<a[j].x&&a[i].y>a[j].y)||(a[i].x>a[j].x&&a[i].y<a[j].y)||(a[i].x==a[j].x))
       {a0=a[i];
        a1=a[j];
        mij.x=(a0.x+a1.x)/2;
        mij.y=(a0.y+a1.y)/2;
        d.x=abs(mij.x-a0.x);
        d.y=abs(mij.y-a0.y);
        a2.x=mij.x-d.y;
        a2.y=mij.y-d.x;
        st=1;dr=n;
        gas=0;
        while(st<=dr)
         {m=(st+dr)/2;
          if(a[m].x==a2.x&&a[m].y==a2.y){gas=m;break;}
          if(a[m].x<a2.x||(a[m].x==a2.x&&a[m].y<a2.y))st=m+1;
                                                 else dr=m-1;}
        if(gas)
          {a3.x=mij.x+d.y;
           a3.y=mij.y+d.x;
           st=1;dr=n;
           gas=0;
           while(st<=dr)
            {m=(st+dr)/2;
             if(a[m].x==a3.x&&a[m].y==a3.y){gas=m;break;}
             if(a[m].x<a3.x||(a[m].x==a3.x&&a[m].y<a3.y))st=m+1;
                                                    else dr=m-1;}
           if(gas)++nr;}}
 printf("%ld",nr);
 return 0;
}