Cod sursa(job #8412)

Utilizator stef2nStefan Istrate stef2n Data 24 ianuarie 2007 18:54:20
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.89 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;
  }

inline int verif_ec(long long a, long long b, long long c, int x, int y)
  {
   return a*x+b*y+c==0;
  }

inline int de_aceeasi_parte(long long a, long long b, long long c, int x1, int y1, int x2, int y2)
  {
   return (a*x1+b*y1+c) * (a*x2+b*y2+c) > 0;
  }

int verifica(punct p1, punct p2)
  {
   long long a,b,c,a1,b1,c1;
   int difx,dify;
   punct p3,p3prim,p4,p4prim;

   difx=p1.x-p2.x;
   dify=p1.y-p2.y;

   a=p1.y-p2.y;
   b=p2.x-p1.x;
   c=p1.x*p2.y-p2.x*p1.y;

   a1=b;
   b1=-a;
   c1=a*p1.y-b*p1.x;

   p3.x=p1.x+dify;
   p3prim.x=p1.x-dify;
   p3.y=p1.y+difx;
   p3prim.y=p1.y-difx;
   if(!verif_ec(a1,b1,c1,p3.x,p3.y))
     {
      p3.y=p1.y-difx;
      p3prim.y=p1.y+difx;
     }

   c1=a*p2.y-b*p2.x;

   p4.x=p1.x+dify;
   p4prim.x=p1.x-dify;
   p4.y=p1.y+difx;
   p4prim.y=p1.y-difx;
   if(!verif_ec(a1,b1,c1,p4.x,p4.y))
     {
      p4.y=p1.y-difx;
      p4prim.y=p1.y+difx;
     }

   if(!de_aceeasi_parte(a,b,c,p3.x,p3.y,p4.x,p4.y))
     {
      punct aux=p3;
      p3=p3prim;
      p3prim=aux;
     }

   return (cauta(0,n-1,p3) && cauta(0,n-1,p4)) + (cauta(0,n-1,p3prim) && cauta(0,n-1,p4prim));
  }


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;
}