Cod sursa(job #8421)

Utilizator stef2nStefan Istrate stef2n Data 24 ianuarie 2007 19:15:19
Problema Patrate 3 Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define infile "patrate3.in"
#define outfile "patrate3.out"
#define NMAX 1005
struct punct{int x,y;};

FILE *fin,*fout;
int n;
punct p[NMAX];

void citire()
  {
   int i,poz,lung;
   char numar[20];
   fin=fopen(infile,"r");
   fscanf(fin,"%d\n",&n);
   for(i=0;i<n;i++)
      {
       fscanf(fin,"%s ",&numar);
       lung=strlen(numar);
       poz=0;
       p[i].x=0;
       while(numar[poz]!='.')
            {
             p[i].x=p[i].x*10+(numar[poz]-'0');
             poz++;
            }
       poz++;
       while(poz<lung)
            {
             p[i].x=p[i].x*10+(numar[poz]-'0');
             poz++;
            }

       fscanf(fin,"%s\n",&numar);
       lung=strlen(numar);
       poz=0;
       p[i].y=0;
       while(numar[poz]!='.')
            {
             p[i].y=p[i].y*10+(numar[poz]-'0');
             poz++;
            }
       poz++;
       while(poz<lung)
            {
             p[i].y=p[i].y*10+(numar[poz]-'0');
             poz++;
            }
      }
   fclose(fin);
  }

inline int cmp(const void *ma, const void *mb)
  {
   punct a=*((punct *)ma);
   punct b=*((punct *)mb);
   if(a.x<b.x)
     return -1;
   if(a.x>b.x)
     return 1;
   return -(a.y<b.y)+(a.y>b.y);
  }

inline int cauta(int li, int ls, punct ppp)
  {
   if(li>ls)
     return 0;
   int mij=(li+ls)/2;
   if(p[mij].x<ppp.x)
     return cauta(mij+1,ls,ppp);
   if(p[mij].x>ppp.x)
     return cauta(li,mij-1,ppp);
   if(p[mij].y<ppp.y)
     return cauta(mij+1,ls,ppp);
   if(p[mij].y>ppp.y)
     return cauta(li,mij-1,ppp);
   return 1;
  }

int verifica(punct p1, punct p2)
  {
   int difx=p2.x-p1.x;
   int dify=p2.y-p1.y;
   punct p3,p4,p5,p6;

   if(dify>=0)
     {
      p3.x=p1.x+dify;
      p3.y=p1.y-difx;
      p4.x=p2.x+dify;
      p4.y=p2.y-difx;

      p5.x=p1.x-dify;
      p5.y=p1.y+difx;
      p6.x=p2.x-dify;
      p6.y=p2.y+difx;
     }
   else
     {
      p3.x=p1.x-dify;
      p3.y=p1.y+difx;
      p4.x=p2.x-dify;
      p4.y=p2.y+difx;

      p5.x=p1.x+dify;
      p5.y=p1.y-difx;
      p6.x=p2.x+dify;
      p6.y=p2.y-difx;
     }

   return (cauta(0,n-1,p3) && cauta(0,n-1,p4)) + (cauta(0,n-1,p5) && cauta(0,n-1,p6));
  }


int main()
{
int i,j,count=0;
citire();
qsort(p,n,sizeof(punct),cmp);
for(i=0;i<n;i++)
   for(j=i+1;j<n;j++)
      count+=verifica(p[i],p[j]);
fout=fopen(outfile,"w");
fprintf(fout,"%d\n",count/4);
fclose(fout);
return 0;
}