Cod sursa(job #374258)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 16 decembrie 2009 15:40:15
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.09 kb
#include <iostream>
#include <string>
#include <vector>

using namespace std;

#define PI pair<int,int>
#define x first
#define y second
#define LL long long
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define PB push_back
#define MKP make_pair
#define min(a,b)((a)<(b)?(a):(b)) 
#define max(a,b)((a)>(b)?(a):(b)) 
#define maxbuf 65536

vector <PI> pct,seg;

//FILE*fin=fopen("poligon.in","r");

int N,M,ind;

char buf[maxbuf];

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

inline int readnr()
{
       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 ap_seg(PI p1,PI p2,PI p0)
{
      LL a1=p1.x-p0.x,
         a2=p2.x-p0.x,
         b1=p1.y-p0.y,
         b2=p2.y-p0.y;
       
      if(a1*b2==a2*b1 && p0.x>=min(p1.x,p2.x) && p0.x<=max(p1.x,p2.x)
      && p0.y>=min(p1.y,p2.y) && p0.y<=max(p1.y,p2.y)) return 1;
      return 0;      
}

inline int semn(PI p1,PI p2,PI p0)
{
      LL a1=p1.x-p0.x,
         a2=p2.x-p0.x,
         b1=p1.y-p0.y,
         b2=p2.y-p0.y;
         
      if(a1*b2-a2*b1<0) return -1;
      else if(a1*b2-a2*b1>0) return 1;
           return 0;    
}

inline int intersect(PI p1,PI p2,PI p3,PI p4)
{
      if(semn(p1,p2,p3)!=semn(p1,p2,p4) && semn(p3,p4,p1)!=semn(p3,p4,p2)) return 1;
      return 0; 
}

int main()
{
      int xx,yy; 
    
      freopen("poligon.in","r",stdin);
      freopen("poligon.out","w",stdout);
    
      //refbuf();
      /*
      N=readnr();
      M=readnr();
      */
      
      scanf("%d %d",&N,&M);
      
      FOR(i,1,N)
      {
        /*
        xx=readnr();
        yy=readnr();
        */
        
        scanf("%d %d",&xx,&yy);
        
        seg.PB(MKP(xx,yy));
      }  
      
      FOR(i,1,M)
      {
        /*
        xx=readnr();
        yy=readnr();
        */
        
        scanf("%d %d",&xx,&yy);
        
        pct.PB(MKP(xx,yy));
      }
      
      int ans=0;
      
      FOR(i,0,M-1)
      {
        int ok=0; 
                  
        FOR(j,0,N-2)
          if(ap_seg(seg[j],seg[j+1],pct[i]))
          {
            ok=1;
            break;
          }
          
        if(ap_seg(seg[N-1],seg[0],pct[i])) ok=1;
        
        if(ok) 
        {
          ++ans;
          continue;
        }  
        
        PI cobra=MKP(pct[i].x,-666);
        
        FOR(j,0,N-2)
          if(intersect(seg[j],seg[j+1],pct[i],cobra)) ++ok;
         
        if(intersect(seg[N-1],seg[0],pct[i],cobra)) ++ok;
         
        if(ok%2) ++ans;   
      }
      
      printf("%d\n",ans);
    
      return 0;
}