Pagini recente » Cod sursa (job #381343) | Cod sursa (job #1187519) | Cod sursa (job #3191045) | Cod sursa (job #2879546) | Cod sursa (job #2914861)
/// Preset de infoarena
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
const int maxN = 805;
int n, q, a[maxN], ans;
double med;
bool vert;
vector <int> v[maxN];
struct point
{
int cx, cy;
} pct[maxN];
double calc(point x, point y, double med)
{
return x.cy + 1.0 * (y.cy - x.cy) * (med - x.cx) / (y.cx - x.cx);
}
bool cmp(int x, int y)
{
return (calc(pct[x], pct[x + 1], med) < calc(pct[y], pct[y + 1], med));
}
int arie(point a, point b, point c)
{
/// ax ay 1 )
/// bx by 1 ) => d = ax * by + ay * cx + bx * cy - by * cx - ay * bx - ax * cy
/// cx cy 1 )
return a.cx * b.cy + a.cy * c.cx + b.cx * c.cy - b.cy * c.cx - a.cy * b.cx - a.cx * c.cy;
}
bool check(int x, point p)
{
int S = 0;
if(pct[x].cx < pct[x + 1].cx || (pct[x].cx == pct[x + 1].cx && pct[x].cy < pct[x + 1].cy))
S = arie(pct[x], pct[x + 1], p);
else
S = arie(pct[x + 1], pct[x], p);
if(S == 0)
vert = 1;
return (S >= 0);
}
int main()
{
fin >> n >> q;
for(int i = 1; i <= n; i++)
{
fin >> pct[i].cx >> pct[i].cy;
a[i] = pct[i].cx;
}
pct[n + 1] = pct[1];
sort(a + 1, a + n + 1);
a[0] = -1;
int k = 0;
for(int i = 1; i <= n; i++)
if(a[i] != a[k])
a[++k] = a[i];
a[k + 1] = a[k] + 1000;
for(int i = 1; i <= k; i++)
{
for(int j = 1; j <= n; j++)
if((pct[j].cx <= a[i] && a[i + 1] <= pct[j + 1].cx) || (pct[j + 1].cx <= a[i] && a[i + 1] <= pct[j].cx))
v[i].push_back(j);
med = (double)(a[i] + a[i + 1]) / 2;
sort(v[i].begin(), v[i].end(), cmp);
}
for(int i = 1; i <= q; i++)
{
point p;
fin >> p.cx >> p.cy;
int poz = 0, aux = -1;
for(int i = (1 << 10); i > 0; i >>= 1)
if(poz + i <= k && a[poz + i] < p.cx)
poz += i;
vert = 0;
for(int i = (1 << 10); i > 0; i >>= 1)
if(aux + i < v[poz].size() && check(v[poz][aux + i], p))
aux += i;
aux++;
if(aux % 2 == 1 || vert)
ans++;
}
fout << ans << '\n';
return 0;
}