Pagini recente » Cod sursa (job #1835044) | Cod sursa (job #1154927) | Cod sursa (job #841745) | Cod sursa (job #1123646) | Cod sursa (job #1288544)
#include <cmath>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 805;
const int MAX_X = 60005;
vector< pair<int, int> > v[MAX_X];
struct Point {
int x, y;
} a[MAX_N];
double pos;
vector<int> place[MAX_N];
inline double get_y(int i, double pos) {
return a[i].y + 1.0 * (a[i + 1].y - a[i].y) * (pos - a[i].x) / (a[i + 1].x - a[i].x);
}
inline bool cmp(const int &a, const int &b) {
return get_y(a, pos) < get_y(b, pos);
}
inline bool exists(const vector< pair<int, int> > &v, int y) {
int left = 0, right = v.size() - 1, last = v.size() - 1;
while (left <= right) {
int middle = (left + right) / 2;
if (v[middle].second >= y) {
last = middle;
right = middle - 1;
} else {
left = middle + 1;
}
}
return v[last].first <= y && y <= v[last].second;
}
int main() {
ifstream fin("poligon.in");
ofstream fout("poligon.out");
int n, q;
fin >> n >> q;
vector<int> lines;
for (int i = 1; i <= n; ++ i) {
fin >> a[i].x >> a[i].y;
lines.push_back(a[i].x);
}
sort(lines.begin(), lines.end());
lines.erase(unique(lines.begin(), lines.end()), lines.end());
int m = lines.size() - 1; ///number of regions
a[0].x = a[n].x; a[0].y = a[n].y;
for (int i = 0; i < n; ++ i) {
if (a[i].x == a[i + 1].x) {
v[a[i].x].push_back(make_pair(min(a[i].y, a[i + 1].y), max(a[i].y, a[i + 1].y)));
} else {
for (int j = 0; j < m; ++ j) {
if (min(a[i].x, a[i + 1].x) <= lines[j] && lines[j + 1] <= max(a[i].x, a[i + 1].x)) {
place[j].push_back(i);
}
}
}
}
for (int i = 0; i < m; ++ i) {
pos = (lines[i] + lines[i + 1]) * 0.5;
sort(place[i].begin(), place[i].end(), cmp);
}
for (int i = 0; i < MAX_X; ++ i) {
sort(v[i].begin(), v[i].end());
}
int count = 0;
for (int i = 1; i <= q; ++ i) {
int x, y;
fin >> x >> y;
if (x < lines.front() || x > lines.back()) {
continue;
}
if (!v[x].empty() && exists(v[x], y)) {
++ count;
continue;
}
int left = 1, right = m, pos = m;
while (left <= right) {
int middle = (left + right) / 2;
if (lines[middle] >= x) {
pos = middle;
right = middle - 1;
} else {
left = middle + 1;
}
}
-- pos;
left = 0; right = place[pos].size() - 1; int last = 0;
while (left <= right) {
int middle = (left + right) / 2;
if (get_y(place[pos][middle], 1.0 * x) >= y) {
last = middle;
right = middle - 1;
} else {
left = middle + 1;
}
}
if (last % 2 == 1 || (fabs(y - get_y(place[pos][last], 1.0 * x)) < 1.e-6)) {
++ count;
}
}
fout << count << "\n";
return 0;
}