Cod sursa(job #42324)

Utilizator g3ppyStoian Vlad g3ppy Data 29 martie 2007 09:09:52
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <stdio.h>
#include <fstream.h>
FILE *fout;

struct pct{double x,y;
	  };
pct a[1001],b[1001];
int n,i,j,d,s,mij,ok,p,v[1001],m1,m2;


int comp(double a,double b)

    {
    if (a-b<0.000001&&a-b>-0.000001) return 0;
    else if (a-b>0.00001) return 1;
    return -1;
    }



void merge (int l, int r)
{int m=(l+r)>>1,i,j,k;
if (l==r) return;

merge(l,m);
merge(m+1,r);
for (i=l,j=m+1,k=l;i<=m||j<=r;)
    {
    if (j>r||(i<=m&&a[i].x<a[j].x))
       b[k++]=a[i++];
    else if (j>r||(i<=m&&a[i].x==a[j].x))
	    {
	    if (a[i].y<a[j].y)
	       b[k++]=a[i++];
	    else b[k++]=a[j++];
	    }

    else b[k++]=a[j++];

    }
for (k=l;k<=r;k++) a[k]=b[k];

}

int main()
{double mijx,mijy,dx,dy,x0,y0,x1,y1,x2,x3,y2,y3;
int m;
ifstream fin("patrate3.in");
fout=fopen("patrate3.out","wt");
fin>>n;
for (i=0;i<n;i++)
    fin>>a[i].x>>a[i].y;
merge(0,n-1);
for (i=0;i<n-1;i++)
   for (j=i+1;j<n;j++)
       {
       if ((v[i]==0&&v[j]==0)||(v[i]!=v[j]))
       {
       x0=a[i].x;
       x1=a[j].x;
       y0=a[i].y;
       y1=a[j].y;
       mijx=(x0+x1)/2;
       mijy=(y0+y1)/2;
       dx=mijx-x0;
       dy=mijy-y0;
       if(dx<0) dx*=-1;
       if(dy<0) dy*=-1;
       if (comp(y0,y1)==-1)
	  {
	  x2=(mijx+dy);
	  y2=(mijy-dx);
	  x3=(mijx-dy);
	  y3=(mijy+dx);
	  }
      else{
	  x2=(mijx-dy);
	  y2=(mijy-dx);
	  x3=(mijx+dy);
	  y3=(mijy+dx);
	  }
       ok=0;
       s=0;
       d=n-1;
       while (m!=d-1)
	     {m=(s+d)>>1;
	     if (comp(a[s].x,x2)==0)
		if (comp(a[s].y,y2)==0)
		  {
		  ok++;
		  m1=s;
		  break;
		  }
	     if (comp(a[d].x,x2)==0)
		if (comp(a[d].y,y2)==0)
		  {
		  ok++;
		  m1=d;
		  break;
		  }

	     if(comp(a[m].x,x2)==-1)
	       s=m;
	     else if(comp(a[m].x,x2)==1)
	       d=m;
	     else
	       {
	       if (comp(a[m].y,y2)==0)
		  {
		  ok++;
		  m1=m;
		  break;
		  }
	       else if (comp(a[m].y,y2)==-1)
		    s=m;
	       else d=m;
	       }

	     }
       s=0;
       d=n-1;
       m=n/2;
       while (m!=d-1&&ok==1)
	     {m=(s+d)>>1;
	     if (comp(a[s].x,x3)==0)
		if (comp(a[s].y,y3)==0)
		  {
		  ok++;
		  m2=s;
		  break;
		  }
	     if (comp(a[d].x,x3)==0)
		if (comp(a[d].y,y3)==0)
		  {
		  ok++;
		  m2=d;
		  break;
		  }

	     if(comp(a[m].x,x3)==-1)
	       s=m;
	     else if(comp(a[m].x,x3)==1)
	       d=m;
	     else
	       {
	       if (comp(a[m].y,y3)==0)
		  {
		  ok++;
		  m2=m;
		  break;
		  }
	       else if (comp(a[m].y,y3)==-1)
		    s=m;
	       else d=m;
	       }

	     }
	if (ok==2)
	   {
	   p++;
	   v[m1]=p;
	   v[m2]=p;
	   }
	}
       }

fprintf(fout,"%d\n",p);
fcloseall();
return 0;
}