Cod sursa(job #348545)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 16 septembrie 2009 00:10:36
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include<iostream>
#include<string>

using namespace std;

#define maxbuf 65536
#define nm 60005
#define mm 805

FILE*fin=fopen("poligon.in","r");
FILE*fout=fopen("poligon.out","w");

int ind,vfx[nm],vfy[nm],ix[mm],iy[mm],n,m;

char buf[maxbuf];

inline void refbuf()
{
       int ans=fread(buf,1,maxbuf,fin);
       
       if(ans<maxbuf) buf[ans]=0;
       
       ind=0;
}

inline int getnr()
{
       int ans=0;
       
       one:
           while(ind < maxbuf && !isdigit(buf[ind])) ind++;
           if(ind==maxbuf)
           {
             refbuf();
             goto one;
           }
      two:
          while(ind < maxbuf && isdigit(buf[ind])) 
          {
            ans=ans*10+buf[ind]-'0';
            ind++;
          }     
          if(ind==maxbuf)
          {
            refbuf();
            goto two;
          }
          
      return ans;    
}

inline int ceva(int a)
{
     if(a==0) return 0;
     if(a<0) return -1;
     if(a>0) return 1; 
}

inline int semn(int x1,int y1,int x2,int y2,int x,int y)
{
      return ceva((x-x1)*(y2-y1)-(x2-x1)*(y-y1)); 
}

inline int intersect(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4)
{
       int ok1=0,ok2=0;
       
       int p1=semn(x1,y1,x2,y2,x3,y3);
       int p2=semn(x1,y1,x2,y2,x4,y4);
       
       //if(p1==0||p2==0) ok1=1;
       if(p1==0||p2==0) return 0;
       if(p1!=p2) ok1=1;
       
       if(!ok1) return 0;
       
       p1=semn(x3,y3,x4,y4,x1,y1);
       p2=semn(x3,y3,x4,y4,x2,y2);
       
       //if(p1==0||p2==0) ok2=1;
       if(p1==0||p2==0) return 0;
       if(p1!=p2) ok2=1;
       
       if(!ok2) return 0;
       
       return 1;
}

int main()
{
    int i,j;
    
    refbuf();
    
    n=getnr();
    m=getnr();
    
    for(i=1;i<=n;i++)
    {
      vfx[i]=getnr();
      vfy[i]=getnr();
    }  
    
    for(i=1;i<=m;i++)
    {
      ix[i]=getnr();
      iy[i]=getnr();
    }
    
    int fans=0;
    
    for(i=1;i<=m;++i)
    {
      int nr_laturi=0;
      
      int x1=ix[i],y1=iy[i];
      int x2=x1,y2=-1;
      
      for(j=1;j<=n;++j)
        if(intersect(x1,y1,x2,y2,vfx[j],vfy[j],vfx[j%n+1],vfy[j%n+1])) ++nr_laturi;
      
      if(nr_laturi%2) ++fans;  
    }
    
    fprintf(fout,"%d",fans);
    
    fclose(fin);
    fclose(fout);
    
    return 0;
}