Pagini recente » Cod sursa (job #113611) | Cod sursa (job #888728) | Cod sursa (job #2923479) | Cod sursa (job #1344701) | Cod sursa (job #2310579)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("poligon.in");
ofstream out("poligon.out");
const int NMAX = 8 * 1e2 + 10;
int n, m;
int res;
int indx;
int i, j;
int a[1 + NMAX];
int b[1 + NMAX];
int c[1 + NMAX];
int x[1 + NMAX];
int aux[1 + NMAX];
double slope[1 + NMAX];
bool found;
vector < int > strip[1 + NMAX];
pair < int, int > v[1 + NMAX];
pair < int, int > q;
inline bool cmp(int a, int b) {
if(slope[a] * (x[i] + x[i + 1]) + 2 * aux[a] < slope[b] * (x[i] + x[i + 1]) + 2 * aux[b])
return true;
else
return false;
}
inline bool check_data(int pos, pair < int, int > query) {
if(a[pos] * query.first + b[pos] * query.second + c[pos] == 0)
found = true;
if(query.second >= slope[pos] * query.first + aux[pos])
return true;
else
return false;
}
int main()
{
in >> n >> m;
for(i = 1; i <= n; i++) {
in >> v[i].first >> v[i].second;
x[i] = v[i].first;
}
v[n + 1] = v[1];
indx = 1;
sort(x + 1, x + n + 1);
for(i = 1; i <= n; i++) {
if(x[i] != x[i - 1]) {
x[++indx] = x[i];
}
}
x[indx + 1] = 0;
for(i = 1; i <= n; i++) {
a[i] = v[i + 1].second - v[i].second;
b[i] = v[i].first - v[i + 1].first;
c[i] = -(a[i] * v[i].first + b[i] * v[i].second);
slope[i] = -1.0 * a[i] / b[i];
aux[i] = -1.0 * c[i] / b[i];
}
for(i = 1; i <= indx; i++) {
for(j = 1; j <= n; j++)
if(x[i] >= min(v[j].first, v[j + 1].first))
if(x[i] < max(v[j].first, v[j + 1].first))
strip[i].push_back(j);
sort(strip[i].begin(), strip[i].end(), cmp);
}
for(int qu = 1; qu <= m; qu++) {
in >> q.first >> q.second;
if(q.first < x[1] || q.first > x[indx])
continue;
found = false;
int step;
for(step = 1024, i = 0; step > 0; step >>= 1)
if(i + step <= indx && x[i + step] < q.first)
i += step;
for(step = 1024, j = 0; step > 0; step >>= 1)
if(j + step <= strip[i].size() && check_data(strip[i][j + step - 1], q))
j += step;
if(j % 2 == 1 || found == true)
res++;
}
out << res << '\n';
in.close();
out.close();
return 0;
}