Pagini recente » Cod sursa (job #2425294) | Cod sursa (job #713140) | Cod sursa (job #1340417) | Cod sursa (job #2012417) | Cod sursa (job #616095)
Cod sursa(job #616095)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const char InFile[]="poligon.in";
const char OutFile[]="poligon.out";
const int MinX=-1;
const int MaxX=60111;
const int MaxN=1024;
const int WINDING=1;
ifstream fin(InFile);
ofstream fout(OutFile);
struct point
{
int x,y;
};
struct line
{
point A,B;
};
struct cmp_line
{
inline bool operator() (const line &a, const line &b)
{
return a.A.y+a.B.y<b.A.y+b.B.y;
}
};
struct strip
{
int xmin,xmax;
vector<line> l;
};
int N,M;
point p[MaxN];
vector<strip> s;
vector<int> v;
inline long long det(const point &a, const point &b, const point &c)
{
return (long long)(b.x-a.x)*(long long)(c.y-a.y)-(long long)(b.y-a.y)*(long long)(c.x-a.x);
}
inline int sgn(const point &a, const point &b, const point &c)
{
long long val=det(a,b,c);
if(val<0)
{
return -1;
}
else if(val>0)
{
return 1;
}
return 0;
}
int main()
{
fin>>N>>M;
v.push_back(MinX);
for(register int i=1;i<=N;++i)
{
fin>>p[i].x>>p[i].y;
v.push_back(p[i].x);
}
p[N+1]=p[1];
v.push_back(MaxX);
sort(v.begin(),v.end());
for(register int i=1;i<=N+1;++i)
{
if(v[i-1]==v[i])
{
continue;
}
strip st;
st.xmin=v[i-1];
st.xmax=v[i];
for(register int i=1;i<=N;++i)
{
int xmin=min(p[i].x,p[i+1].x);
int xmax=max(p[i].x,p[i+1].x);
if(xmin<=st.xmin && st.xmax<=xmax)
{
line l;
l.A=p[i];
l.B=p[i+1];
point UP;
UP.x=(l.A.x+l.B.x)>>1;
UP.y=((l.A.y+l.B.y)>>1)+MaxX;
if(sgn(l.A,l.B,UP)!=WINDING)
{
swap(l.A,l.B);
}
if(l.A.x!=l.B.x)
{
st.l.push_back(l);
}
}
}
sort(st.l.begin(),st.l.end(),cmp_line());
s.push_back(st);
}
int sol=0;
for(register int i=1;i<=M;++i)
{
int px,py;
fin>>px>>py;
point pq;
pq.x=px; pq.y=py;
int p=0;
int u=s.size()-1;
while(p<=u)
{
int m=p+((u-p)>>1);
if(px<=s[m].xmin)
{
u=m-1;
}
else
{
p=m+1;
}
}
int sind=u;
if(0<sind && sind<(int)(s.size()-1))
{
p=0;
u=s[sind].l.size()-1;
while(p<=u)
{
int m=p+((u-p)>>1);
int sg=sgn(s[sind].l[m].A,s[sind].l[m].B,pq);
if(sg==0)
{
++sol;
goto NEXT;
}
if(sg==WINDING)
{
p=m+1;
}
else
{
u=m-1;
}
}
if(u%2==0)
{
++sol;
}
}
NEXT:
int a=0;
}
fin.close();
fout<<sol;
fout.close();
return 0;
}