Pagini recente » Cod sursa (job #2570747) | Cod sursa (job #2451626) | Cod sursa (job #1014256) | Cod sursa (job #265331) | Cod sursa (job #2878686)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
const int NMAX(805), MMAX(60005);
int n, m, despZone[NMAX], nr;
double med;
bool vert;
struct punct
{
int x, y;
} pnct[NMAX];
vector<int> DrepZone[NMAX];
double work(punct a, punct b)
{
return a.y + (b.y - a.y) * (med - a.x) / ((double)b.x - a.x);
}
inline bool cmp(int a, int b)
{
return work(pnct[a], pnct[a + 1]) < work(pnct[b], pnct[b + 1]);
}
void procesare()
{
sort(despZone + 1, despZone + n + 1);
despZone[0] = -1;
for(int i = 1; i <= n; ++i)
if(despZone[i] != despZone[nr])
despZone[++nr] = despZone[i];
pnct[n + 1] = pnct[1];
despZone[nr + 1] = despZone[nr] + 1000;
for(int i = 1; i <= nr; ++i)
{
for(int j = 1; j <= n; ++j)
if((pnct[j].x <= despZone[i] && despZone[i + 1] <= pnct[j + 1].x) || (pnct[j + 1].x <= despZone[i] && despZone[i + 1] <= pnct[j].x))
DrepZone[i].push_back(j);
med = (double)(despZone[i] + despZone[i + 1]) / (double)2;
sort(DrepZone[i].begin(), DrepZone[i].end(), cmp);
}
}
long long det(punct a, punct b, punct c)
{
return 1LL * a.x * b.y + 1LL * b.x * c.y + 1LL * c.x * a.y - 1LL * a.x * c.y - 1LL * b.x * a.y - 1LL * c.x * b.y;
}
inline bool comp(punct a, punct b)
{
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
inline bool ok(int i, int x, int y)
{
long long d = 0;
if(comp(pnct[i], pnct[i + 1]))
d = det(pnct[i], pnct[i + 1], {x, y});
else d = det(pnct[i + 1], pnct[i], {x, y});
if(d == 0)
{
vert = 1;
return 1;
}
return (d > 0);
}
int main()
{
fin >> n >> m;
for(int i = 1; i <= n; ++i)
{
fin >> pnct[i].x >> pnct[i].y;
despZone[i] = pnct[i].x;
}
procesare();
int rez = 0;
for(int i = 1; i <= m; ++i)
{
int x, y;
fin >> x >> y;
int st = 1;
int dr = nr;
int best = 0;
while(st <= dr)
{
int mij = (st + dr) / 2;
if(despZone[mij] < x)
{
best = mij;
st = mij + 1;
}
else dr = mij - 1;
}
st = vert = 0;
int best2 = -1;
dr = DrepZone[best].size() - 1;
while(st <= dr)
{
int mij = (st + dr) / 2;
if(ok(DrepZone[best][mij], x, y))
{
best2 = mij;
st = mij + 1;
}
else dr = mij - 1;
}
++best2;
rez += ((best2 & 1) || vert);
}
fout << rez << '\n';
return 0;
}