Pagini recente » Cod sursa (job #1643401) | Cod sursa (job #446322) | Cod sursa (job #1494141) | Cod sursa (job #2518462) | Cod sursa (job #1992478)
#include <bits/stdc++.h>
#define eps 1e-6
using namespace std;
struct Punct
{
int x, y;
} v[810];
struct Dreapta
{
int a, b, c;
void init(const Punct& p1, const Punct& p2)
{
a = p1.y - p2.y;
b = p2.x - p1.x;
c = p1.x * p2.y - p2.x * p1.y;
}
};
int vx[810];
vector<Dreapta> vf[810];
int st, dr, n, lvx;
double calc_y(Dreapta d, int x)
{
return double(-d.a * x - d.c) / d.b;
}
bool cmp(Dreapta da, Dreapta db)
{
double ya = calc_y(da, (st + dr) / 2);
double yb = calc_y(db, (st + dr) / 2);
return ya < yb;
}
int cautb_vx(int x)
{
int st = 0, dr = lvx - 1, mij;
while(st <= dr)
{
mij = (st + dr) / 2;
if(vx[mij] == x)
return mij;
else
if(vx[mij] < x)
st = mij + 1;
else dr = mij - 1;
}
return mij;
}
int cautb_vx2(int x)
{
int st = 0, dr = lvx - 1, mij;
while(st <= dr)
{
mij = (st + dr) / 2;
if(vx[mij] < x && x < vx[mij + 1])
return mij;
else
if(vx[mij] < x)
st = mij + 1;
else
dr = mij - 1;
}
return -1;//mij;
}
int cautb_fs(const vector<Dreapta>& v, Punct p)
{
int st = 0, dr = v.size() - 1, mij, rez = -1;
while(st <= dr)
{
mij = (st + dr) / 2;
double y = calc_y(v[mij], p.x);
if(abs(y - p.y) <= eps)
return 1;
else
if(y < p.y)
{
st = mij + 1;
rez = mij;
}
else
dr = mij - 1;
}
return (rez + 1) % 2;
}
int main()
{
freopen("poligon.in", "r", stdin);
freopen("poligon.out", "w", stdout);
int k;
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i++)
{
scanf("%d%d", &v[i].x, &v[i].y);
vx[i] = v[i].x;
}
v[n] = v[0];
sort(vx, vx + n);
lvx = 1;
for(int i = 1; i < n; i++)
{
if(vx[i] != vx[i - 1])
vx[lvx++] = vx[i];
}
for(int i = 0; i < n; i++)
{
Dreapta dreapta;
dreapta.init(v[i], v[i + 1]);
int fs = cautb_vx(v[i].x);
int fd = cautb_vx(v[i + 1].x);
if(fs > fd) swap(fs, fd);
for(; fs < fd; fs++)
vf[fs].push_back(dreapta);
}
for(int i = 0; i < lvx - 1; i++)
{
st = vx[i];
dr = vx[i + 1];
sort(vf[i].begin(), vf[i].end(), cmp);
}
int rez = 0;
for(int i = 0; i < k; i++)
{
Punct p;
scanf("%d%d", &p.x, &p.y);
if(p.x < vx[0] || p.x > vx[lvx - 1])
continue;
int fas = cautb_vx2(p.x);
if(fas != -1)
rez += cautb_fs(vf[fas], p);
else
{
fas = cautb_vx(p.x);
int r1 = cautb_fs(vf[fas - 1], p);
int r2 = cautb_fs(vf[fas], p);
rez += r1 | r2;
}
}
printf("%d", rez);
return 0;
}