Pagini recente » Cod sursa (job #165312) | Cod sursa (job #2720004) | Cod sursa (job #2922282) | Cod sursa (job #63971) | Cod sursa (job #2102695)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define x first
#define y second
using namespace std;
ifstream si("poligon.in");
ofstream so("poligon.out");
pair<int,int> p[805];
vector<int> v[805];
int t[805];
long double mij;
int col;
long long det(pair<int,int> a,pair<int,int> b,pair<int,int> c)
{
return 1LL*a.x*b.y+1LL*b.x*c.y+1LL*c.x*a.y-1LL*a.x*c.y-1LL*b.x*a.y-1LL*c.x*b.y;
}
long double eval(pair<int,int> a,pair<int,int> b,double x)
{
return a.y+(b.y-a.y)*(mij-a.x)/((double)b.x-a.x);
}
bool cmp(int a,int b)
{
return eval(p[a],p[a+1],mij)<eval(p[b],p[b+1],mij);
}
bool ok(int i,pair<int,int> a)
{
long long tmp=det(min(p[i],p[i+1]),max(p[i],p[i+1]),a);
if(tmp==0)
{
col=1;
return 1;
}
return tmp>0;
}
int main()
{
int n,m;
si>>n>>m;
for(int i=1;i<=n;++i)
{
si>>p[i].x>>p[i].y;
t[i]=p[i].x;
}
p[n+1]=p[1];
t[0]=-1;
sort(t+1,t+n+1);
int k=0;
for(int i=1;i<=n;++i)
{
if(t[k]!=t[i])
{
t[++k]=t[i];
}
}
t[k+1]=t[k]+100;
for(int i=1;i<=k;++i)
{
for(int j=1;j<=n;++j)
{
if((p[j].x<=t[i]&&t[i+1]<=p[j+1].x)||(p[j+1].x<=t[i]&&t[i+1]<=p[j].x))
v[i].push_back(j);
}
mij=0.5*(t[i]+t[i+1]);
sort(v[i].begin(),v[i].end(),cmp);
}
int r=0;
for(int i=1;i<=m;++i)
{
pair<int,int> q;
si>>q.x>>q.y;
int pos=0;
for(int pas=1<<9;pas;pas>>=1)
if(pos+pas<=k&&t[pos+pas]<q.x)
pos+=pas;
int rez=-1;
col=0;
for(int pas=1<<9;pas;pas>>=1)
if(rez+pas<v[pos].size()&&ok(v[pos][rez+pas],q))
rez+=pas;
++rez;
r+=(rez&1)||col;
}
so<<r<<'\n';
return 0;
}