Pagini recente » Cod sursa (job #1564815) | Cod sursa (job #675424) | Cod sursa (job #2128559) | Cod sursa (job #2265291) | Cod sursa (job #1748035)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define MAXN 850
#define MAXM 60050
using namespace std;
struct coord
{
int x, y;
coord(int x = 0, int y = 0) : x(x), y(y) { }
bool operator()(coord a, coord b)
{
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
};
int n, m;
coord polygon[MAXN];
coord infra[MAXM];
double a[MAXN], b[MAXN], c[MAXN];
vector<int> xes;
vector<int> banda[MAXN];
int cmpxind;
const double EPS = 0.000000008;
inline bool equals(double e, double f)
{
return (e-f) >= -EPS && (e-f) <= EPS;
}
bool cmp(int i, int j)
{
double y1 = (-c[i] - a[i] * xes[cmpxind]) / b[i];
//double y2 = polygon[i+1].x > xes[cmpxind+1] ? (-c[i] - a[i] * xes[cmpxind+1]) / b[i] : polygon[i+1].y;
double y2 = (-c[i] - a[i] * xes[cmpxind+1]) / b[i];
double yi = (y1+y2); // /2
y1 = (-c[j] - a[j] * xes[cmpxind]) / b[j];
y2 = (-c[j] - a[j] * xes[cmpxind+1]) / b[j];
double yj = (y1+y2); // /2
return yi < yj;
}
void citire()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d %d", &polygon[i].x, &polygon[i].y);
for (int i = 1; i <= m; i++)
scanf("%d %d", &infra[i].x, &infra[i].y);
}
void prepare()
{
/// precalc ecuations
polygon[n+1] = polygon[1];
for (int i = 1; i <= n; i++) {
coord p1 = polygon[i];
coord p2 = polygon[i+1];
a[i] = p1.y - p2.y;
b[i] = p2.x - p1.x;
c[i] = p1.x*p2.y - p2.x*p1.y;
}
vector<int> temp;
for (int i = 1; i <= n; i++)
temp.push_back(polygon[i].x);
sort(temp.begin(), temp.end());
xes.push_back(temp.front());
for (int i = 1; i < n; i++)
if (temp[i] != temp[i-1])
xes.push_back(temp[i]);
xes.push_back(temp.front());
for (int i = 0; i < xes.size()-1; i++) {
cmpxind = i;
for (int j = 1; j <= n; j++) {
coord p1 = polygon[j];
coord p2 = polygon[j%n + 1];
if (min(p1.x, p2.x) <= xes[i] && max(p1.x, p2.x) > xes[i])
banda[i].push_back(j);
}
sort(banda[i].begin(), banda[i].end(), cmp);
//printf("%d\n", banda[i].size());
}
}
bool sub(int lix, coord p, int &ed)
{
if (equals(a[lix]*p.x + b[lix]*p.y + c[lix], 0)) ed = 1;
double y1 = (-c[lix] - a[lix] * p.x) / b[lix];
return (p.y >= y1);
}
void solve()
{
int rez = 0;
for (int i = 1; i <= m; i++) {
int val = 0;
int cs = 1, cf = xes.size()-1;
for (cs; cs < xes.size(); cs <<= 1);
for (int step = cs; step; step >>= 1)
if (val + step < cf && xes[val+step] < infra[i].x)
val += step;
if (infra[i].x < xes[val]) continue;
cf = banda[val].size();
for (cs = 1; cs <= cf; cs <<= 1);
int cate = 0, ed = 0;
for (int step = cs; step; step >>= 1) {
if (cate + step <= cf && sub(banda[val][cate+step-1], infra[i], ed))
cate += step;
}
rez += (ed || (cate & 1));
}
printf("%d", rez);
}
int main()
{
freopen("poligon.in", "r", stdin);
freopen("poligon.out", "w", stdout);
citire();
prepare();
solve();
return 0;
}