Pagini recente » Cod sursa (job #2891989) | Cod sursa (job #1661959) | Cod sursa (job #591975) | Cod sursa (job #676704) | Cod sursa (job #1150598)
#include <cmath>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 805;
vector<int> verticals;
int sz[MAX_N];
int zones[MAX_N][MAX_N];
struct Point {
int x, y;
} points[MAX_N];
struct Line {
int a, b, c;
} lines[MAX_N];
inline double get_distance(double x1, double y1, double x2, double y2) {
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
inline bool on_segment(Point &a, Point &b, double x, double y) {
return fabs(get_distance(1.0 * a.x, 1.0 * a.y, x, y) + get_distance(1.0 * b.x, 1.0 * b.y, x, y) - get_distance(1.0 * a.x, 1.0 * a.y, 1.0 * b.x, 1.0 * b.y)) < 1.e-6;
}
inline double get_y(const int &index, const int &x) {
return -1.0 * (lines[index].c + lines[index].a * x) / lines[index].b;
}
int x1, x2;
inline int compare(const int &a, const int &b) {
double y1, y2;
y1 = -1.0 * (lines[a].c + lines[a].a * (x1 + x2) * 0.5) / lines[a].b;
y2 = -1.0 * (lines[b].c + lines[b].a * (x1 + x2) * 0.5) / lines[b].b;
//cout << "Comparing " << a << "(" << y1 << ") with " << b << "(" << y2 << ")\n";
return y2 - y1 > -1.e-6;
}
int main() {
ifstream fin("poligon.in");
ofstream fout("poligon.out");
int n, queries;
fin >> n >> queries;
for(int i = 0; i < n; ++ i) {
fin >> points[i].x >> points[i].y;
}
for(int i = 0; i < n; ++ i) {
lines[i].a = points[i].y - points[(i + 1) % n].y;
lines[i].b = points[(i + 1) % n].x - points[i].x;
lines[i].c = points[i].x * points[(i + 1) % n].y - points[(i + 1) % n].x * points[i].y;
verticals.push_back(points[i].x);
}
sort(verticals.begin(), verticals.end());
verticals.erase(unique(verticals.begin(), verticals.end()), verticals.end());
int m = static_cast<int>(verticals.size()) - 1; //number of zones
for(int i = 1; i <= m; ++ i) {
for(int j = 0; j < n; ++ j) {
if(lines[j].b == 0) {
continue;
}
double y1, y2;
y1 = -1.0 * (lines[j].c + lines[j].a * verticals[i - 1]) / lines[j].b;
y2 = -1.0 * (lines[j].c - lines[j].a * verticals[i]) / lines[j].b;
if(on_segment(points[j], points[(j + 1) % n], 1.0 * verticals[i - 1], y1) && on_segment(points[j], points[(j + 1) % n], 1.0*verticals[i], y2)) {
zones[i][++ sz[i]] = j;
}
}
x1 = verticals[i - 1]; x2 = verticals[i];
sort(zones[i] + 1, zones[i] + sz[i] + 1, compare);
//for(int j = 0; j < static_cast<int>(zones[i].size()); ++ j) {
// cout << " " << zones[i][j];
//}
//cout << "\n";
}
int answer = 0;
for(int i = 0; i < queries; ++ i) {
int x, y;
fin >> x >> y;
if(x < verticals[0] || x > verticals[m]) {
continue;
}
int zone = 0;
for(int pas = 512; pas; pas >>= 1) {
if(zone + pas <= m && x >= verticals[zone + pas - 1]) {
zone += pas;
}
}
int count = 0;
for(int pas = 512; pas; pas >>= 1) {
if(count + pas <= sz[zone] && y - get_y(zones[zone][count + pas], x) > -1.e-6) {
count += pas;
}
}
if(fabs(y - get_y(zones[zone][count], x)) < 1.e-6 || (count & 1)) {
++ answer;
}
}
fout << answer << "\n";
return 0;
}