Pagini recente » Cod sursa (job #497630) | Cod sursa (job #2841737) | Cod sursa (job #3280191) | Istoria paginii utilizator/valentina506 | Cod sursa (job #3175944)
#include <bits/stdc++.h>
#define EPS 0.000001
using namespace std;
int f[60001];
vector <int> points[60001];
vector <int> verticals;
vector <vector <int>> lines;
struct point{
int x, y;
}v[801];
int n;
double MED;
bool comp(int a, int b){
double K1 = (1.0 * (v[a].y - v[(a + 1) % n].y) / (1.0 * v[a].x - v[(a + 1) % n].x)) * (1.0 * MED - v[a].x) + v[a].y;
double K2 = (1.0 * (v[b].y - v[(b + 1) % n].y) / (1.0 * v[b].x - v[(b + 1) % n].x)) * (1.0 * MED - v[b].x) + v[b].y;
return K1 < K2;
}
int ishigher(double x, double y, int line){
double Y = y;
double _Y = 1.0 * v[line].y - 1.0 * (v[line].x - x) * (v[line].y - v[(line + 1) % n].y) / (v[line].x - v[(line + 1) % n].x);
if(_Y == Y || (x - v[line].x) * (v[line].y - v[(line + 1) % n].y) == (y - v[line].y) * (v[line].x - v[(line + 1) % n].x)) return 0;
if(_Y < Y) return 1;
if(_Y > Y) return -1;
return 0;
}
int sol = 0;
bool check(int i, double x, double y){
int j, pas;
j = 0;
pas = 1 << 9;
while(pas) {
if (j + pas < lines[i].size() && ishigher(x, y, lines[i][j + pas]) > 0) {
j += pas;
}
pas >>= 1;
}
if(ishigher(x, y, lines[i][j]) == 0){
sol++;
return true;
}
else
if(j % 2 == 0) {
sol++;
return true;
}
return false;
}
int main() {
int m, i, j, pas;
freopen("poligon.in", "r", stdin);
freopen("poligon.out", "w", stdout);
scanf("%d%d", &n, &m);
for(i = 0; i < n; i++) {
scanf("%d%d", &v[i].x, &v[i].y);
f[v[i].x] = 1;
points[v[i].x].push_back(v[i].y);
}
for(i = 0; i <= 60000; i++) {
if(f[i]) {
verticals.push_back(i);
sort(points[i].begin(), points[i].end());
}
}
for(i = 1; i < verticals.size(); i++){
vector <int> aux;
for(j = 0; j < n; j++)
if(min(v[j].x, v[(j + 1) % n].x) <= verticals[i - 1] && max(v[j].x, v[(j + 1) % n].x) >= verticals[i] && v[j].x != v[(j + 1) % n].x)
aux.push_back(j);
lines.push_back(aux);
}
for(int k = 0; k < lines.size(); k++){
MED = (1.0 * verticals[k] + verticals[k + 1]) / 2.0;
sort(lines[k].begin(), lines[k].end(), comp);
}
while(m--){
double x, y;
scanf("%lf%lf", &x, &y);
pas = 1 << 16;
i = 0;
while(pas){
if(i + pas < verticals.size() && verticals[i + pas] <= x)
i += pas;
pas >>= 1;
}
if(verticals[i] == x){
bool var = false;
if(i != verticals.size() - 1) {
x += EPS;
var = check(i, x, y);
}
if(!var) {
x -= 2 * EPS;
var = check(i - 1, x, y);
}
}
else{
if(i != verticals.size() - 1)
bool var = check(i,x ,y);
}
}
printf("%d\n", sol);
return 0;
}