Pagini recente » Cod sursa (job #3250167) | Cod sursa (job #3124429) | Profil CiurelVictor | Cod sursa (job #2836636) | Cod sursa (job #3171818)
#include <bits/stdc++.h>
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(int x, int 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;
}
int main() {
int m, i, j, x, y, 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);
}
int sol = 0;
while(m--){
scanf("%d%d", &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){
j = 0;
pas = 1 << 9;
while(pas){
if(j + pas < points[x].size() && points[x][j + pas] <= y)
j += pas;
pas /= 2;
}
if(j % 2 == 0)
sol++;
}
else{
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++;
}
else
if(j % 2 == 0)
sol++;
}
}
printf("%d\n", sol);
return 0;
}