Pagini recente » Cod sursa (job #2676335) | Cod sursa (job #2300341) | Cod sursa (job #924051) | Cod sursa (job #3121739) | Cod sursa (job #1100351)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 805;
const double eps = 1.e-7;
struct PointXY {
double x, y;
} a[MAX_N];
double paralels_to_oy[MAX_N];
double start_x, end_x;
bool compare(const pair<double, double> &a, const pair<double, double> &b) {
double a1 = a.first - a.second;
double b1 = end_x - start_x;
double c1 = a.second * start_x - a.first * end_x;
double a2 = b.first - b.second;
double b2 = end_x - start_x;
double c2 = b.second * start_x - b.first * end_x;
double middle1 = (- c1 - a1 * (start_x + end_x) * 0.5) / b1;
double middle2 = (- c2 - a2 * (start_x + end_x) * 0.5) / b2;
return middle2 - middle1 >= eps;
}
struct Section {
double start_x, end_x;
vector< pair<double, double> > segments;
} sections[MAX_N];
pair<double, double> get_points(PointXY &A, PointXY &B, double x1, double x2) {
double a = A.y - B.y;
double b = B.x - A.x;
double c = A.x * B.y - A.y * B.x;
//a * x1 + b * y1 + c = 0 => y1 = (- c - a * x1) / b
return make_pair((- c - a * x1) / b, (- c - a * x2) / b);
}
vector< pair<int, pair<int, int> > > verticals;
inline int on_verticals(PointXY &p) {
if(verticals.empty()) {
return 0;
}
int left = 0, right = static_cast<int>(verticals.size()) - 1, middle;
while(left <= right) {
middle = (left + right) / 2;
if(verticals[middle].first == p.x) {
break;
} else if(verticals[middle].first < p.x) {
left = middle + 1;
} else {
right = middle - 1;
}
}
if(verticals[middle].first != p.x) {
return 0;
}
return min(verticals[middle].second.first, verticals[middle].second.second) <= p.y &&
p.y <= max(verticals[middle].second.first, verticals[middle].second.second);
}
inline bool above(PointXY &p, Section §ion, int index) {
double a = section.segments[index].first - section.segments[index].second;
double b = section.end_x - section.start_x;
double c = section.start_x * section.segments[index].second - section.end_x * section.segments[index].first;
double y = (- c - a * p.x) / b;
//cout << y << " " << p.y << "\n";
return y - p.y > -eps;
}
int main() {
ifstream fin("poligon.in");
ofstream fout("poligon.out");
int n, m, k = 0;
fin >> n >> m;
for(int i = 0; i < n; ++ i) {
fin >> a[i].x >> a[i].y;
paralels_to_oy[i] = a[i].x;
}
sort(paralels_to_oy, paralels_to_oy + n);
for(int i = 1; i < n; ++ i) {
if(paralels_to_oy[i] != paralels_to_oy[i - 1]) {
++ k;
sections[k].start_x = paralels_to_oy[i - 1];
sections[k].end_x = paralels_to_oy[i];
for(int j = 0; j < n; ++ j) {
if(a[j].x <= sections[k].start_x && sections[k].end_x <= a[(j + 1) % n].x) {
sections[k].segments.push_back(get_points(a[j], a[(j + 1) % n], sections[k].start_x, sections[k].end_x));
}
if(a[j].x >= sections[k].end_x && sections[k].start_x >= a[(j + 1) % n].x) {
sections[k].segments.push_back(get_points(a[j], a[(j + 1) % n], sections[k].start_x, sections[k].end_x));
}
}
}
start_x = sections[i].start_x;
end_x = sections[i].end_x;
sort(sections[i].segments.begin(), sections[i].segments.end(), compare);
}
for(int i = 0; i < n; ++ i) {
if(a[i].x == a[(i + 1) % n].x) {
verticals.push_back(make_pair(a[i].x, make_pair(a[i].y, a[(i + 1) % n].y)));
}
}
sort(verticals.begin(), verticals.end());
int count = 0;
for(int i = 1; i <= m; ++ i) {
PointXY p;
fin >> p.x >> p.y;
if(p.x < sections[1].start_x || p.x > sections[k].end_x) {
fout << "-1\n";
continue;
}
if(on_verticals(p)) {
++ count;
continue;
}
int section = 0;
for(int pas = 512; pas; pas >>= 1) {
if(section + pas <= k && p.x >= sections[section + pas].start_x) {
section += pas;
}
}
//cout << "Section #" << section << "\n";
//for(int i = 0; i < static_cast<int>(sections[section].segments.size()); ++ i) {
// cout << sections[section].segments[i].first << " " << sections[section].segments[i].second << "\n";
//}
int how_many = -1;
for(int pas = 512; pas; pas >>= 1) {
if(how_many + pas < static_cast<int>(sections[section].segments.size()) && !above(p, sections[section], how_many + pas)) {
how_many += pas;
}
}
//cout << how_many << "\n";
if(how_many % 2 == 0) {
++ count;
}
}
fout << count << "\n";
return 0;
}