Pagini recente » Cod sursa (job #2596242) | Cod sursa (job #1981962) | Cod sursa (job #2515708) | Cod sursa (job #2514137) | Cod sursa (job #2327527)
#include <bits/stdc++.h>
using namespace std;
ifstream in("poligon.in");
ofstream out("poligon.out");
typedef long long ll;
const int N = 805;
vector<int> v[N];
bool vertical;
int t[N],n,k;
double mid;
struct pct
{
int x,y;
} p[N];
double eval(pct a, pct b, double m)
{
return a.y+(b.y-a.y)*(m-a.x)/((double)b.x-a.x);
}
bool comp(int x, int y)
{
return eval(p[x],p[x+1],mid)<eval(p[y],p[y+1],mid);
}
ll det(pct a, pct b, pct 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;
}
bool compare(pct a, pct b)
{
if (a.x == b.x)
return a.y<b.y;
return a.x<b.x;
}
bool ok(int i, pct a)
{
ll D;
if (compare(p[i],p[i+1]))
D = det(p[i],p[i+1],a);
else
D = det(p[i+1],p[i],a);
if (!D)
{
vertical = 1;
return 1;
}
return D>0;
}
void precompute()
{
sort(t+1,t+n+1);
t[0] = -1;
p[n+1] = p[1];
for (int i = 1; i<=n; i++)
if (t[i]!=t[k])
t[++k] = t[i];
t[k+1] = t[k]+100;
for (int i = 1; i<=k; i++)
{
for (int j = 1; j<=n; j++)
if ((p[j].x<=t[i]&&t[i+1]<=p[j+1].x)||(p[j+1].x<=t[i]&&t[i+1]<=p[j].x))
v[i].push_back(j);
mid = (double)(t[i]+t[i+1])/2;
sort(v[i].begin(),v[i].end(),comp);
}
}
int main()
{
int m;
in >> n >> m;
for (int i = 1; i<=n; i++)
{
in >> p[i].x >> p[i].y;
t[i] = p[i].x;
}
precompute();
int ans = 0;
for (int i = 1; i<=m; i++)
{
pct c;
in >> c.x >> c.y;
int poz = 0, cnt = -1;
for (int i = 1<<9; i; i>>=1)
if (poz+i<=k && t[poz+i]<c.x)
poz+=i;
vertical = 0;
for (int i = 1<<9; i; i>>=1)
if (cnt+i<v[poz].size() && ok(v[poz][i+cnt],c))
cnt+=i;
cnt++;
ans+=((cnt&1)||(vertical));
}
out << ans;
}