Pagini recente » Monitorul de evaluare | Cod sursa (job #461237) | Cod sursa (job #13421) | Cod sursa (job #2005496) | Cod sursa (job #1593068)
// 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;
}