Pagini recente » Cod sursa (job #1877995) | Cod sursa (job #2019051) | Cod sursa (job #1168635) | Cod sursa (job #1651094) | Cod sursa (job #1746504)
#include <fstream>
#include <algorithm>
#include <vector>
#define fi first
#define se second
#define mp make_pair
#define pi pair<int, int>
using namespace std;
const int kMaxN = 805;
struct Point {
double x, y;
Point() {}
Point(int _x, int _y) : x(_x), y(_y) {}
};
struct Segment {
Point a, b;
Segment() {}
Segment(Point _a, Point _b) : a(_a), b(_b) {}
Point Middle() { return Point((a.x + b.x) / 2, (a.y + b.y) / 2); }
};
struct Line {
double a, b, c;
Line() {}
Line(double _a, double _b, double _c) : a(_a), b(_b), c(_c) {}
Line(Point p1, Point p2) {
a = p1.y - p2.y;
b = p2.x - p1.x;
c = (-1) * a * p1.x + (-1) * b * p1.y;
}
};
double CrossProduct(Point p1, Point p2, Point p3) {
return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}
bool AboveSegment(Point p, Segment s) {
return CrossProduct(s.a, s.b, p) > 0;
}
int n, q;
Point p[kMaxN];
vector<int> x_coords;
vector<vector<Segment>> strips;
int main() {
ifstream f("poligon.in");
ofstream g("poligon.out");
f >> n >> q;
for(int i = 1; i <= n; i++) {
f >> p[i].x >> p[i].y;
x_coords.push_back(p[i].x);
}
sort(x_coords.begin(), x_coords.end());
x_coords.erase(unique(x_coords.begin(), x_coords.end()), x_coords.end());
strips.resize(x_coords.size() - 1);
for(int i = 0; i < x_coords.size() - 1; i++) {
for(int j = 1; j <= n; j++) {
Point p_here = p[j];
Point p_there = (j == n ? p[1] : p[j + 1]);
if(p_here.x > p_there.x)
swap(p_here, p_there);
if(p_here.x == p_there.x)
continue;
if(p_here.x <= x_coords[i] && x_coords[i + 1] <= p_there.x) {
Line seg_line(p_here, p_there);
double y_here = (-1) * (seg_line.a * p_here.x + seg_line.c) / seg_line.b;
double y_there = (-1) * (seg_line.a * p_there.x + seg_line.c) / seg_line.b;
strips[i].push_back(Segment(Point(x_coords[i], y_here), Point(x_coords[i + 1], y_there)));
}
}
}
for(int i = 0; i < strips.size(); i++)
sort(strips[i].begin(), strips[i].end(), [] (Segment s1, Segment s2) { return s1.Middle().y < s2.Middle().y; });
int good_cnt = 0;
while(q--) {
int x, y;
f >> x >> y;
if(x < x_coords.front() || x > x_coords.back())
continue;
int id = lower_bound(x_coords.begin(), x_coords.end(), x) - x_coords.begin() - 1;
int lo = 0, hi = strips[id].size() - 1, mid;
while(lo <= hi) {
mid = (lo + hi) / 2;
if(AboveSegment(Point(x, y), strips[id][mid])) { lo = mid + 1; }
else hi = mid - 1;
}
//t pos = upper_bound(strips[id].begin(), strips[id].end(), Point(x, y), AboveSegment) - strips[id].begin();
int pos = lo;
//g << pos << " pos\n";
good_cnt += (pos & 1);
}
g << good_cnt << '\n';
return 0;
}