Pagini recente » Cod sursa (job #130451) | Cod sursa (job #1839738) | Cod sursa (job #2242533) | Cod sursa (job #1594104) | Cod sursa (job #517078)
Cod sursa(job #517078)
#include <iostream>
#include <fstream>
#include <algorithm>
#define x first
#define y second
#define DN 805
#define DM 60005
using namespace std;
typedef pair<int, int> PER;
int n,m,px[DN],dx[DN],dy[DN],ec[DN],nr[DN],sol;
PER p[DN];
pair<double, int> li[DN][DN];
void precalc() {//dreptele verticale
double a,xnou,ynou;
for(int i=1; i<n; ++i) if(px[i]!=px[i+1]) for(int j=1; j<=n; ++j)
if (((p[j].x<=px[i])&&(p[j+1].x>=px[i+1])) || ((p[j+1].x<=px[i])&&(p[j].x>=px[i+1]))) {//apatine zonei
if (p[j+1].y==p[j].y) ynou=p[j].y;
else {
a=(double)(p[j+1].x-p[j].x)/(p[j+1].y-p[j].y);
xnou=(double)(px[i+1]+px[i])/2-p[j].x;
ynou=(double)p[j].y+xnou/a;
}
li[i][++nr[i]].y=j;
li[i][nr[i]].x=ynou;
}
for(int i=1; i<n; ++i) if(px[i]!=px[i+1]) sort(li[i]+1,li[i]+nr[i]+1);
}
void bs(PER pct) {
if (pct.x<px[1]) return;
int unde=lower_bound(px+1,px+n+1,pct.x)-px-1;
int ls=1,ld=nr[unde],m,semn;
double f;
for(; ls+1<ld; ) {
m=(ls+ld)/2;
if (p[li[unde][m].y].x<p[li[unde][m].y+1].x) semn=1;
else semn=-1;
f=(double)semn*(dy[li[unde][m].y]*pct.x+dx[li[unde][m].y]*pct.y+ec[li[unde][m].y]);
if (f>0) ls=m;
else if (f<0) ld=m;
else ls=ld=m;
}
m=ls;
if (p[li[unde][m].y].x<p[li[unde][m].y+1].x) semn=1;
else semn=-1;
f=(double)semn*(dy[li[unde][m].y]*pct.x+dx[li[unde][m].y]*pct.y+ec[li[unde][m].y]);
if(f<0)--m;
else if(0==f) {
++sol;
return;
}
if (p[li[unde][m+1].y].x<p[li[unde][m+1].y+1].x) semn=1;
else semn=-1;
f=(double)semn*(dy[li[unde][m+1].y]*pct.x+dx[li[unde][m+1].y]*pct.y+ec[li[unde][m+1].y]);
if(f>0) ++m;
else if(0==f) {
++sol;
return;
}
if(m%2) ++sol;
}
int main()
{
ifstream f("poligon.in");
ofstream g("poligon.out");
f>>n>>m;
int i;
for(i=1; i<=n; ++i) {
f>>p[i].x>>p[i].y;
px[i]=p[i].x;
}
p[n+1]=p[1];
sort(px+1,px+n+1);
for(i=1; i<=n; ++i) {
dx[i]=p[i+1].x-p[i].x;
dy[i]=p[i].y-p[i+1].y;
ec[i]=p[i].x*p[i+1].y-p[i+1].x*p[i].y;
}
precalc();
PER z;
for(i=1; i<=m; ++i) {
f>>z.x>>z.y;
bs(z);
}
g<<sol<<'\n';
return 0;
}