Pagini recente » Cod sursa (job #1897743) | Cod sursa (job #2025042) | Cod sursa (job #331852) | Cod sursa (job #892556) | Cod sursa (job #972485)
Cod sursa(job #972485)
#include<fstream>
#include<algorithm>
#include<vector>
#define pb push_back
#define mp make_pair
#define pr pair<double,int>
#define yy first
#define ind second
#define maxn 805
#define maxstep 1024
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
struct point{ int x,y;} v[maxn],p;
struct muchie{ point p1,p2;} vm[maxn];
int n,m,ns,sol;
int vs[maxn],ad[maxn],bd[maxn],cd[maxn];
double i1[maxn],i2[maxn];
vector <pr> sect[maxn];
void cit()
{
int i;
fin>>n>>m;
for(i=1;i<=n;i++){ fin>>v[i].x>>v[i].y; vs[i]=v[i].x;}
v[n+1]=v[1]; v[0]=v[n]; vs[0]=-1;
}
int cmpx(int a,int b) { return a<b; }
int cmps(pr a,pr b) { return a.yy<b.yy; }
double inter(int k,int vx)
{
return i1[k]-i2[k]*vx;
}
void calc(point a,point b,int k)
{
ad[k]=b.y-a.y;
bd[k]=a.x-b.x;
cd[k]=a.y*b.x-a.x*b.y;
i1[k]=-(1.0*cd[k])/bd[k];
i2[k]=(1.0*ad[k])/bd[k];
}
void initialize()
{
int i,j;
double yy1,yy2;
sort(vs+1,vs+n+1,cmpx);
for(i=1;i<=n;i++)
{
if(vs[i]!=vs[i-1])
vs[++ns]=vs[i];
vm[i].p1=v[i]; vm[i].p2=v[i+1];
if(v[i].x>v[i+1].x) swap(vm[i].p1,vm[i].p2);
}
for(i=1;i<=n;i++) calc(vm[i].p1,vm[i].p2,i);
for(i=1;i<ns;i++)
{
for(j=1;j<=n;j++)
{
if(vm[j].p1.x>vs[i]) continue;
if(vm[j].p2.x<=vs[i]) continue;
yy1=inter(j,vs[i]);
yy2=inter(j,vs[i+1]);
sect[i].pb(mp((yy1+yy2)/2,j));
}
sort(sect[i].begin(),sect[i].end(),cmps);
}
}
long long int side(int k,point c)
{
return ad[k]*c.x+bd[k]*c.y+cd[k];
}
void solve()
{
int step,i,nrs,lim;
for(int k=1;k<=m;k++)
{
fin>>p.x>>p.y;
if(p.x<vs[1] || p.x>vs[ns]) continue;
step=maxstep;
for(i=0;step;step>>=1)
if(i+step<=ns && vs[i+step]<=p.x)
i+=step;
nrs=i; if(nrs==ns) nrs--;
lim=sect[nrs].size()-1;
step=maxstep;
for(i=-1;step;step>>=1)
if(i+step<=lim && side(sect[nrs][i+step].ind,p)<=0)
i+=step;
if(side(i,p)==0) {sol++; continue;}
if((i+1)%2==1) sol++;
}
}
int main()
{
freopen("poligon.in","r",stdin);
freopen("poligon.out","w",stdout);
cit();
initialize();
solve();
fout<<sol;
fin.close();
fout.close();
return 0;
}