Pagini recente » Cod sursa (job #2676251) | Cod sursa (job #2128681) | Cod sursa (job #2453477) | Cod sursa (job #48497) | Cod sursa (job #3157470)
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("poligon.in");
ofstream cout("poligon.out");
const int DELTA = 6e4;
const int MAX = 2100;
typedef pair<double, double> Point;
Point point[MAX];
vector<int> functii[MAX];
int benzi[MAX], good;
double med;
int n, q;
int ans;
static inline double calc_y(const int& x) {
return (double)(point[x].second + (double)(point[x + 1].second - point[x].second) / (point[x + 1].first - point[x].first) * (med - point[x].first));
}
static inline int arie(const Point& x, const Point& y, const Point& z) {
return x.first * (y.second - z.second) + y.first * (z.second - x.second) + z.first * (x.second - y.second);
}
static inline bool check(int x, int y, int z) {
int s;
if(point[z].first < point[z + 1].first || (point[z].first == point[z + 1].first && point[z].second < point[z + 1].second))
s = arie(point[z], point[z + 1], {x, y});
else s = arie(point[z + 1], point[z], {x, y});
if(s == 0)
good = 1;
return (s >= 0);
}
int main()
{
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> point[i].first >> point[i].second;
benzi[i] = point[i].first;
}
point[n + 1] = point[1];
sort(benzi + 1, benzi + n + 1);
benzi[0] = -1;
int m = 0;
for(int i = 1; i <= n; i++)
if(benzi[m] != benzi[i])
benzi[++m] = benzi[i];
benzi[m + 1] = benzi[m] + DELTA;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++)
if ((point[j].first <= benzi[i] && benzi[i + 1] <= point[j + 1].first) || (point[j + 1].first <= benzi[i] && benzi[i + 1] <= point[j].first))
functii[i].push_back(j);
med = (double)(benzi[i] + benzi[i + 1]) / 2;
sort(functii[i].begin(), functii[i].end(), [](const int& A, const int& B) {
return calc_y(A) < calc_y(B);
} );
}
int x, y;
while(q--) {
cin >> x >> y;
good = 0;
int banda = 0;
for(int pas = 20; pas >= 0; pas--)
if(banda + (1 << pas) <= m && benzi[banda + (1 << pas)] < x)
banda += (1 << pas);
int intersecti = -1;
for(int pas = 20; pas >= 0; pas--)
if(intersecti + (1 << pas) < functii[banda].size() && check(x, y, functii[banda][intersecti + (1 << pas)]))
intersecti += (1 << pas);
ans += !(intersecti & 1) + (good * (intersecti & 1));
}
cout << ans << '\n';
return 0;
}