Pagini recente » Cod sursa (job #2620363) | Cod sursa (job #238100) | Cod sursa (job #140479) | Cod sursa (job #2513479) | Cod sursa (job #3155227)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in ("poligon.in");
ofstream out ("poligon.out");
const int max_size = 1e3 + 1090, max_v = 6e4;
pair <double, double> pct[max_size];
int benzi[max_size], coincide;
double med;
vector <int> inq[max_size];
double calc_y (int x)
{
return (double)(pct[x].second + (double)(pct[x + 1].second - pct[x].second) / (pct[x + 1].first - pct[x].first) * (med - pct[x].first));
}
bool cmp (int x, int y)
{
return calc_y(x) < calc_y(y);
}
int arie (pair <double, double> x, pair <double, double> y, pair <double, double> z)
{
return x.first * (y.second - z.second) + y.first * (z.second - x.second) + z.first * (x.second - y.second);
}
bool check (int x, int y, int z)
{
int s;
if (pct[z].first < pct[z + 1].first || (pct[z].first == pct[z + 1].first && pct[z].second < pct[z + 1].second))
{
s = arie(pct[z], pct[z + 1], {x, y});
}
else
{
s = arie(pct[z + 1], pct[z], {x, y});
}
if (s == 0)
{
coincide = 1;
}
return (s >= 0);
}
int main ()
{
int n, q;
in >> n >> q;
for (int i = 1; i <= n; i++)
{
in >> pct[i].first >> pct[i].second;
benzi[i] = pct[i].first;
}
pct[n + 1] = pct[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] + max_v;
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if ((pct[j].first <= benzi[i] && benzi[i + 1] <= pct[j + 1].first) || (pct[j + 1].first <= benzi[i] && benzi[i + 1] <= pct[j].first))
{
inq[i].push_back(j);
}
}
med = (double)(benzi[i] + benzi[i + 1]) / 2;
sort(inq[i].begin(), inq[i].end(), cmp);
}
int ans = 0;
while (q--)
{
int x, y;
in >> x >> y;
coincide = 0;
int poz1 = 0, e = 20;
while (e >= 0)
{
if (poz1 + (1 << e) <= m && benzi[poz1 + (1 << e)] < x)
{
poz1 += (1 << e);
}
e--;
}
int poz2 = -1;
e = 20;
while (e >= 0)
{
if (poz2 + (1 << e) < inq[poz1].size() && check(x, y, inq[poz1][poz2 + (1 << e)]))
{
poz2 += (1 << e);
}
e--;
}
poz2++;
if (poz2 % 2 == 1 || coincide == 1)
{
ans++;
}
}
out << ans;
in.close();
out.close();
return 0;
}
/*
4 3
0 0
0 100
100 100
100 0
50 50
100 50
100 110
*/