Pagini recente » Cod sursa (job #1840727) | Clasament atafedtsorp | Cod sursa (job #3175808) | Cod sursa (job #2806253) | Cod sursa (job #1202986)
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int Nmax = 805, INF = 0x3f3f3f3f;
class Point {
public:
int x, y;
Point(const int _x = 0, const int _y = 0):
x(_x),
y(_y) {}
bool operator < (const Point &e) const {
if (x != e.x) return x < e.x;
return y < e.y;
}
};
class Segment {
public:
Point a, b;
Segment(const Point _a = Point(0, 0), const Point _b = Point(0, 0)):
a(_a),
b(_b) {}
bool operator < (const Segment &e) const {
return a.x < e.a.x;
}
bool isVertical() const {
return a.x == b.x;
}
void swap() {
Point aux = a;
a = b;
b = aux;
}
};
Point Points[Nmax];
Segment Segments[Nmax];
vector<int> BSegments[Nmax], VerticalSegments[Nmax];
long long Det(const Point o, const Point a, const Point b)
{
return 1LL * (a.x - o.x) * (b.y - o.y) - 1LL * (b.x - o.x) * (a.y - o.y);
}
int Nr;
struct comp {
bool operator()(const int &a, const int &b) const {
const double pca = (double)(Segments[a].b.y - Segments[a].a.y) * (Nr - Segments[a].a.x) / (Segments[a].b.x - Segments[a].a.x) + Segments[a].a.y;
const double pcb = (double)(Segments[b].b.y - Segments[b].a.y) * (Nr - Segments[b].a.x) / (Segments[b].b.x - Segments[b].a.x) + Segments[b].a.y;
return pca < pcb;
}
};
struct compVertical {
bool operator()(const int &a, const int &b) const {
return Segments[a].b.x < Segments[b].b.x;
}
};
int main()
{
freopen("poligon.in", "r", stdin);
freopen("poligon.out", "w", stdout);
int N, Q;
scanf("%d%d", &N, &Q);
vector<int> Xs(1, -INF);
for (int i = 1; i <= N; i++)
{
scanf("%d%d", &Points[i].x, &Points[i].y);
Xs.push_back(Points[i].x);
}
for (int i = 1; i < N; i++)
Segments[i] = Segment(Points[i], Points[i + 1]);
Segments[N] = Segment(Points[N], Points[1]);
for (int i = 1; i <= N; i++)
if (Segments[i].a.x > Segments[i].b.x)
Segments[i].swap();
else if (Segments[i].isVertical() && Segments[i].a.y > Segments[i].b.y)
Segments[i].swap();
sort(Xs.begin(), Xs.end());
Xs.erase(unique(Xs.begin(), Xs.end()), Xs.end());
for (int i = 1; i < int(Xs.size()); i++)
{
BSegments[i].push_back(0);
VerticalSegments[i].push_back(0);
for (int j = 1; j <= N; j++)
{
if (Segments[j].isVertical() && Segments[j].a.x == Xs[i])
{
VerticalSegments[i].push_back(j);
continue;
}
if (Segments[j].a.x <= Xs[i - 1] && Xs[i] <= Segments[j].b.x)
BSegments[i].push_back(j);
}
Nr = Xs[i];
sort(BSegments[i].begin() + 1, BSegments[i].end(), comp());
sort(VerticalSegments[i].begin() + 1, VerticalSegments[i].end(), compVertical());
}
int Sol = 0;
while (Q--)
{
Point P;
scanf("%d%d", &P.x, &P.y);
int posx = lower_bound(Xs.begin() + 1, Xs.end(), P.x) - Xs.begin();
if (posx == int(Xs.size())) continue;
bool ok = 0;
if (P.x == Xs[posx])
{
int posy = 0;
for (int step = (1 << 9); step; step >>= 1)
{
if ((posy | step) < int(VerticalSegments[posx].size()) && Segments[VerticalSegments[posx][posy | step]].b.y < P.y)
posy |= step;
}
posy++;
if (posy < int(VerticalSegments[posx].size()))
{
const Segment S = Segments[VerticalSegments[posx][posy]];
if (S.a.y <= P.y) ok = 1;
}
}
int posy = 0;
for (int step = (1 << 9); step; step >>= 1)
{
if ((posy | step) < int(BSegments[posx].size()) && Det(P, Segments[BSegments[posx][posy | step]].b, Segments[BSegments[posx][posy | step]].a) < 0)
posy |= step;
}
posy++;
if (posy < int(BSegments[posx].size()) && !Det(P, Segments[BSegments[posx][posy]].b, Segments[BSegments[posx][posy]].a))
ok = 1;
else
ok |= ((posy & 1) ^ 1);
if (ok) Sol++;
}
printf("%d\n", Sol);
}