Cod sursa(job #1593068)

Utilizator tdr_drtTdr Drt tdr_drt Data 8 februarie 2016 11:41:58
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 kb
// interzis copiilor sub 18 ani
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");

int n,m,rez,seen[801];

struct ball{
  int x,y;
}p[801],t;

struct balls{
 int cur,prev,next;
}a[801];

bool soo_big(balls a,balls b){
   return p[a.cur].x<p[b.cur].x;
}

int is_so_tiny_i_cant_find_it(int x){
   int st,dr,m;
   st=dr=m=0;
   dr=n;
   while(st<dr){
    m=(st+dr)/2;
    if(p[a[m].cur].x>x) dr=m-1;
    else st=m+1;
   }
   return dr;
}

bool i_can_feel_it_on_me(double x1,double y1,double x,double y,double xx,double yy){
   double xb,yb;

   if(x==xx){
    xb=x;
    yb=y1;
   }
   else if(y==yy){
    if(y1=y) return true;
    return false;
   }
   else{
   xb=yb=(double)0;
   xb=(x*((yy-y)/xx-x)+y1-y)/((yy-y)/(xx-x));
   yb=((yy-y)/(xx-x))*(xb-x)+y;
   }

   if(xb>=x1){
    double maxx,maxy,minx,miny;
    miny=min(y,yy);
    minx=min(x,xx);
    maxx=max(x,xx);
    maxy=max(y,yy);
    if(xb>=minx&&xb<=maxx&&yb>=miny&&yb<=maxy) return true;
   }

  return false;
}

bool is_inside(int x,int y,int cont){
  int nr;
  nr=0;

  for(int i=is_so_tiny_i_cant_find_it(x);i<=n;i++){
     if(p[a[i].cur].x==x&&p[a[i].cur].y==y) return true;
     else{
        if(seen[a[i].cur]==cont&&seen[a[i].prev]==cont);
         else
        if(i_can_feel_it_on_me(x,y,p[a[i].cur].x,p[a[i].cur].y,p[a[i].prev].x,p[a[i].prev].y)==true) {seen[a[i].cur]=cont; seen[a[i].prev]=cont; nr++;}
          else {seen[a[i].cur]=cont; seen[a[i].prev]=cont;}

        if(seen[a[i].cur]==cont&&seen[a[i].next]==cont);
         else
        if(i_can_feel_it_on_me(x,y,p[a[i].cur].x,p[a[i].cur].y,p[a[i].next].x,p[a[i].next].y)==true) {seen[a[i].cur]=cont; seen[a[i].next]=cont; nr++;}
           else {seen[a[i].cur]=cont; seen[a[i].next]=cont;}
     }
  }

  if(nr%2==1) return true;
  return false;
}

int main(){

 f>>n>>m;

 for(int i=1;i<=n;i++)
 {
     f>>p[i].x>>p[i].y;
     a[i].prev=i-1;
     a[i].cur=i;
     a[i].next=i+1;
 }

 a[n].next=1;
 a[1].prev=n;

 sort(a+1,a+n+1,soo_big);

 //for(int i=1;i<=n;i++) g<<a[i].cur<<" ";

 for(int i=1;i<=m;i++){
    f>>t.x>>t.y;
    if(is_inside(t.x,t.y,i)==true) rez++;
 }

 g<<rez;

 return 0;
}