Pagini recente » Cod sursa (job #604190) | Cod sursa (job #3287273) | Cod sursa (job #2763342) | Cod sursa (job #82660) | Cod sursa (job #1716903)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int N_MAX = 805;
class Point {
public:
double x;
double y;
Point() {}
Point(double _x, double _y) : x(_x), y(_y) {}
};
class Segment {
public:
Point a;
Point b;
Segment() {}
Segment(Point _a, Point _b) : a(_a), b(_b) {}
};
int n, m;
Point p[N_MAX];
vector<int> X;
vector<Segment> Z[N_MAX];
Point Inters(Point A, Point B, int x) {
double a = A.y - B.y;
double b = B.x - A.x;
double c = - a * A.x - b * A.y;
return Point(x, (-a * x - c) / b);
}
inline bool trigOrder(Point A, Point B, Point C) {
return 1LL * (B.x - A.x) * (C.y - A.y) > 1LL * (C.x - A.x) * (B.y - A.y);
}
int main() {
ifstream f("poligon.in");
ofstream g("poligon.out");
f >> n >> m;
for(int i = 1; i <= n; i++) {
int x, y;
f >> x >> y;
p[i] = Point(x, y);
}
p[n + 1] = p[1];
for(int i = 1; i <= n; i++)
X.push_back(p[i].x);
sort(X.begin(), X.end());
X.erase(unique(X.begin(), X.end()), X.end());
int nzones = X.size() - 1;
for(int i = 0; i < nzones; i++) {
for(int j = 1; j <= n; j++) {
if(p[j].x <= X[i] && X[i + 1] <= p[j + 1].x) {
Z[i].push_back(Segment(Inters(p[j], p[j + 1], X[i]), Inters(p[j], p[j + 1], X[i + 1])));
}
}
}
for(int i = 0; i < nzones; i++) {
for(auto &s : Z[i]) {
if(s.a.x > s.b.x) {
swap(s.a, s.b);
}
}
}
for(int i = 0; i < nzones; i++) {
sort(Z[i].begin(), Z[i].end(), [] (Segment s1, Segment s2) {
return (s1.a.y + s1.b.y) / 2 - (s2.a.y + s2.b.y) / 2 < -1e-6;
});
}
int ans = 0;
while(m--) {
int x, y;
Point pt;
f >> x >> y;
pt = Point(x, y);
if(x < X.front() || x > X.back())
continue;
int px = upper_bound(X.begin(), X.end(), x) - X.begin() - 1;
int py = Z[px].end() - upper_bound(Z[px].begin(), Z[px].end(), pt, [] (Point pt, Segment s) {
return 1LL * (s.b.x - s.a.x) * (pt.y - s.a.y) < 1LL * (pt.x - s.a.x) * (s.b.y - s.a.y);
}) + 1;
if(py & 1)
ans++;
}
g << ans << '\n';
return 0;
}