Pagini recente » Cod sursa (job #2371597) | Cod sursa (job #2180276) | Cod sursa (job #1229693) | Cod sursa (job #447756) | Cod sursa (job #3337085)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
long long n,m,i,j,ok,s;
struct pct{
long long x,y;
bool operator==(pct a){
return a.x==x&&a.y==y;
}
};
struct edge{
pct a,b;
long long ymin,ymax;
};
pct v[810];
edge e[810];
pct mi={60010,1};
long long cross(pct A,pct B,pct C){
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
long long dot(pct A,pct B,pct C){
return (B.x-A.x)*(C.x-A.x)+(B.y-A.y)*(C.y-A.y);
}
bool cmp(edge A,edge B){
return A.ymin<B.ymin;
}
int main(){
fin>>n>>m;
for(i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
v[0]=v[n];
v[n+1]=v[1];
for(i=1;i<=n;i++){
e[i].a=v[i];
e[i].b=v[i+1];
e[i].ymin=min(v[i].y,v[i+1].y);
e[i].ymax=max(v[i].y,v[i+1].y);
}
sort(e+1,e+n+1,cmp);
for(i=1;i<=m;i++){
pct p;
fin>>p.x>>p.y;
mi.y=p.y+1;
ok=0;
int lim=upper_bound(e+1,e+n+1,p.y,[](long long val,const edge&ed){
return val<ed.ymin;
})-(e+1);
for(j=0;j<lim;j++){
if(p.y>=e[j+1].ymax) continue;
pct A=e[j+1].a;
pct B=e[j+1].b;
long long r1=cross(mi,p,A);
long long r2=cross(mi,p,B);
long long r3=cross(A,B,mi);
long long r4=cross(A,B,p);
if(p==A||p==B){
ok=1;
break;
}
if(r4==0&&dot(A,B,p)>0&&dot(B,A,p)>0){
ok=1;
break;
}
if(r1*r2<0&&r3*r4<0)
ok=1-ok;
}
if(ok) s++;
}
fout<<s;
return 0;
}