Pagini recente » Cod sursa (job #1770580) | Cod sursa (job #1657917) | Cod sursa (job #2702465) | Cod sursa (job #2456164) | Cod sursa (job #415316)
Cod sursa(job #415316)
#include<fstream>
#include<algorithm>
#include<vector>
#define x first
#define y second
using namespace std;
const char iname[]="poligon.in";
const char oname[]="poligon.out";
const int maxn=805;
ifstream f(iname);
ofstream g(oname);
typedef pair<int,int> point;
typedef pair<point,point> line;
point a[maxn],b[maxn];
pair<vector<line>,int> E[maxn];
int i,j,n,m,x,y,step,band,rez;
long long area(point a,point b,point c)
{
return 1LL*a.x*(b.y-c.y)+1LL*b.x*(c.y-a.y)+1LL*c.x*(a.y-b.y);
}
bool fcomp(line a,line b)
{
if(a.x<a.y)
return area(a.x,a.y,b.y)>=0;
return area(a.y,a.x,b.y)>=0;
}
int main()
{
f>>n>>m;
for(i=1;i<=n;++i)
f>>a[i].x>>a[i].y,b[i]=a[i];
sort(b+1,b+n+1);
for(i=1;i<=n;++i)
E[i].y=b[i].x;
E[0].y=-1;
E[n+1].y=70000;
a[0]=a[n];
for(i=0;i<n;++i)
for(j=1;j<=n;++j)
if((a[i].x<E[j+1].y&&a[i+1].x>=E[j].y)||(a[i+1].x<E[j+1].y&&a[i].x>=E[j].y))
E[j].x.push_back(make_pair(a[i],a[i+1]));
for(i=1;i<=n;++i)
sort(E[i].x.begin(),E[i].x.end(),fcomp);
for(i=1;i<=m;++i)
{
f>>x>>y;
for(step=1;step<n;step<<=1);
for(j=0;step;step>>=1)
if(j+step<=n&&E[j+step].y<=x)
j+=step;
band=j;
for(step=1;step<E[band].x.size();step<<=1);
for(j=0;step;step>>=1)
if(j+step<E[band].x.size()&&fcomp(E[band].x[j],make_pair(make_pair(x,y),make_pair(x,y))));
j+=step;
if(E[band].x.size()==0||(j==0&&fcomp(E[band].x[j],make_pair(make_pair(x,y),make_pair(x,y)))==false))
++j;
if(j&1);
else
++rez;
}
g<<rez<<"\n";
f.close();
g.close();
return 0;
}