Pagini recente » Cod sursa (job #374126) | Cod sursa (job #2466731) | Cod sursa (job #1826386) | Cod sursa (job #1356140) | Cod sursa (job #1140448)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
const double eps = 1e-9;
int N, M;
int sol, X, Y;
int banda[801], nrbanda, nowbanda;
double ecm[801], ecn[801];
vector<int> V[801];
bool viz[60001];
struct puncte
{
int x, y;
};
puncte P[801];
struct dreapta
{
int a, b;
long long c;
};
dreapta Ec[801];
double gety(int now, int xnow)
{
return ecm[now] * xnow / 2.0 + ecn[now];
}
bool cmp(int nr1, int nr2)
{
int xmid = banda[nowbanda] + banda[nowbanda + 1];
double y1 = gety(nr1, xmid);
double y2 = gety(nr2, xmid);
return y1 < y2;
//return y2 - y1 > eps;
}
int GetBanda()
{
/*
int l = 0, r = nrbanda + 1;
while (r - l > 1)
{
int mid = (l + r) / 2;
if (banda[mid] <= X && X < banda[mid + 1])
return mid;
if (banda[mid] <= X)
l = mid;
else
r = mid;
}
return l;
*/
int st = 1, dr = nrbanda - 1, mij;
while (st <= dr)
{
mij = (st+dr) >> 1;
if (banda[mij] <= X && X < banda[mij+1])
return mij;
if (banda[mij] <= X)
st = mij+1;
else
dr = mij-1;
}
return nrbanda;
}
int solve()
{
if (X < banda[1] || X > banda[nrbanda])
return 0;
int nowbanda = GetBanda();
if (nowbanda == nrbanda)
{
if (viz[Y])
return 1;
return 0;
}
int l = -1, r = V[nowbanda].size();
while (r - l > 1)
{
int mid = (l + r) / 2;
int now = V[nowbanda][mid];
long long det = 1LL * Ec[now].a * X + 1LL * Ec[now].b * Y + Ec[now].c;
if (det == 0)
return 1;
if (det > 0LL)
l = mid;
else
r = mid;
}
l += 1;
if (l == V[nowbanda].size())
return 0;
if (r == -1)
return 0;
if (l & 1)
return 1;
return 0;
/*
int st = 0, dr = V[nowbanda].size() - 1, mij;
while (st <= dr)
{
mij = (st+dr)>>1;
int ind = V[nowbanda][mij];
long long det = 1LL*Ec[ind].a * X + 1LL*Ec[ind].b*Y + Ec[ind].c;
if (det == 0)
return 1;
if (det > 0LL) // e deasupra
st = mij+1;
else
dr = mij-1;
}
if (st == V[nowbanda].size())
return 0;
if (dr == -1)
return 0;
if ((st & 1) == 1)
return 1;
return 0;
*/
}
int main()
{
fin >> N >> M;
for (int i = 1; i <= N; ++i)
{
fin >> P[i].x >> P[i].y;
banda[i] = P[i].x;
}
P[N + 1] = P[1];
sort(banda + 1, banda + N + 1);
banda[++nrbanda] = banda[1];
for (int i = 2; i <= N; ++i)
if (banda[i] != banda[nrbanda])
banda[++nrbanda] = banda[i];
for (int i = 1; i <= N; ++i)
{
/*
Ec[i].a = P[i + 1].y - P[i].y;
Ec[i].b = P[i].x - P[i + 1].x;
Ec[i].c = P[i + 1].x * P[i].y - P[i].x * P[i + 1].y;
*/
if (P[i].x < P[i+1].x)
{
Ec[i].a = P[i].y - P[i+1].y;
Ec[i].b = P[i+1].x - P[i].x;
Ec[i].c = 1LL * P[i].x * P[i+1].y - 1LL * P[i+1].x * P[i].y;
}
else
{
Ec[i].a = - P[i].y + P[i+1].y;
Ec[i].b = - P[i+1].x + P[i].x;
Ec[i].c = -1LL * P[i].x * P[i+1].y + 1LL * P[i+1].x * P[i].y;
}
ecm[i] = -1.0 * Ec[i].a / Ec[i].b;
ecn[i] = -1.0 * Ec[i].c / Ec[i].b;
}
for (int i = 1; i <= nrbanda; ++i)
{
for (int j = 1; j <= N; ++j)
if (min(P[j].x, P[j + 1].x) <= banda[i] && banda[i] < max(P[j].x, P[j + 1].x))
V[i].push_back(j);
nowbanda = i;
sort(V[i].begin(), V[i].end(), cmp);
}
for (int i = 1; i <= N; ++i)
{
if (max(P[i].x, P[i + 1].x) == banda[nrbanda])
{
if (min(P[i].x, P[i + 1].x) == banda[nrbanda])
{
int liminf = min(P[i].y, P[i + 1].y);
int limsup = max(P[i].y, P[i + 1].y);
for (int j = liminf; j <= limsup; ++j)
viz[j] = true;
}
else if (P[i].x == banda[nrbanda])
viz[P[i].y] = true;
else
viz[P[i + 1].y] = true;
}
}
while (M)
{
fin >> X >> Y;
sol += solve();
--M;
}
fout << sol << '\n';
fin.close();
fout.close();
return 0;
}