Pagini recente » Cod sursa (job #1518078) | Cod sursa (job #508448) | Rating Bacula Ianis (ianis98) | Cod sursa (job #359336) | Cod sursa (job #1140698)
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#define x first
#define y second
#define inf 100000
#define point pair<int,int>
using namespace std;
ifstream fin ("poligon.in");
ofstream fout ("poligon.out");
pair<int,int>p[801],q;
struct segment
{
int a,b,c;
float midpoint;
}poly[801];
struct division
{
int x1,x2;
vector<segment> S;
}d[801];
bool viz[60001];
int n,m,cnt,t,r;
struct cmp
{
bool operator () (const division &a, const division &b)
{
return a.x1 < b.x1;
}
};
float yintersect (segment s, int X)
{
return (float)(-s.a*X - s.c)/s.b;
}
struct cmp2
{
bool operator () (const segment &s1, const segment &s2)
{
return s1.midpoint < s2.midpoint;
}
};
int det (point a, point b, point c)
{
return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
bool bs2 (int wh)
{
int lo = -1, hi = d[wh].S.size();
while (hi - lo > 1)
{
int mid = (lo + hi)/2;
int val = d[wh].S[mid].a*q.x + d[wh].S[mid].b*q.y + d[wh].S[mid].c;
if (val == 0)
return 1;
if (val > 0)
lo = mid;
else hi = mid;
}
if ((lo&1)==0)
return 1;
return 0;
}
void bs ()
{
int lo = 0, hi = t;
while (hi - lo > 1)
{
int mid = (lo + hi)/2;
if (q.x <= d[mid].x2)
hi = mid;
else lo = mid;
}
if (bs2 (hi))
++cnt;
}
int main()
{
fin>>n>>m;
for (int i=1; i<=n; ++i)
{
fin>>p[i].x>>p[i].y;
if (!viz[p[i].x])
{
d[++t].x1 = p[i].x;
viz[p[i].x] = 1;
}
}
for (int j=1; j<=n; ++j)
{
int jj = j+1;
if (jj == n+1)
jj = 1;
poly[j].a = p[j].y - p[jj].y;
poly[j].b = p[jj].x - p[j].x;
poly[j].c = p[jj].y*p[j].x - p[jj].x*p[j].y;
if (p[j].x > p[jj].x)
{
poly[j].a = -poly[j].a;
poly[j].b = -poly[j].b;
poly[j].c = -poly[j].c;
}
}
sort (d+1,d+t+1,cmp () );
for (int i=1; i<t; ++i)
{
point refa = make_pair(d[i].x1,inf), refb = make_pair(d[i].x1,-inf);
d[i].x2 = d[i+1].x1;
for (int j=1; j<=n; ++j)
{
int jj = j+1;
if (jj == n+1)
jj = 1;
point a = p[j], b = p[jj];
if (a.x > b.x)
swap (a,b);
if (det (refa,refb,b) > 0 && det(refa,refb,a) <= 0)
{
d[i].S.push_back (poly[j]);
float y1 = yintersect (poly[j],d[i].x1);
float y2 = yintersect (poly[j],d[i].x2);
d[i].S[d[i].S.size()-1].midpoint = (y1+y2)/2;
}
}
r = i;
sort (d[i].S.begin(),d[i].S.end(),cmp2 () );
}
for (int i=1; i<=m; ++i)
{
fin>>q.x>>q.y;
bs ();
}
fout<<cnt<<"\n";
}