Challenge: Polygon
Scor cont: 80.0 / 80
Submission status: Accepted
Submission score: 1.0
Submission ID: 464776966
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/polygon/problem
Cerinta
There are N points on X-Y plane with integer coordinates (xi, yi). You are given a set of polygons with all of its edges parallel to the axes (in other words, all angles of the polygons are 90 degree angles and all lines are in the cardinal directions. There are no diagonals). For each polygon your program should find the number of points lying inside it. A point located on the border of polygon is also considered to be inside the polygon.
**Input Format**
The first line contains two integers N and Q. The next line contains N space-separated integer coordinates (xi,yi). Q queries follow. Each query consists of a single integer Mi in the first line, followed by Mi space separated integer coordinates (x[i][j],y[i][j]) specifying the boundary of the query polygon in clock-wise order.
- Polygon is an alternating sequence of vertical line segments and horizontal line segments.
- Polygon has Mi edges, where (x[i][j],y[i][j]) is connected to (x[i][(j+1)%Mi], y[i][(j+1)%Mi].
- For each 0 <= j < Mi, either x[i][(j+1)%Mi] == x[i][j] or y[i][(j+1)%Mi] == y[i][j] but not both.
- It is guaranteed that the polygon is not self-intersecting.
**Output Format**
For each query output the number of points inside the query polygon in a separate line.
**Constraints**
1 <= N <= 20,000
1 <= Q <= 20,000
4 <= Mi <= 20
-200,000 <= x[i][j],y[i][j] <= 200,000
**Sample Input #1**
16 2
0 0
0 1
0 2
0 3
1 0
1 1
1 2
1 3
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3
8
0 0
0 1
1 1
1 2
0 2
0 3
3 3
3 0
4
0 0
0 1
1 1
1 0
**Sample Output #1:**
16
4
**Sample Input #2:**
6 1
1 1
3 3
3 5
5 2
6 3
7 4
10
1 3
1 6
4 6
4 3
6 3
6 1
4 1
4 2
3 2
3 3
**Sample Output #2:**
4
Cod sursa
#include <bits/stdc++.h>
using namespace std;
struct Fenwick2DStatic {
vector<int> xs;
vector<vector<int>> bit;
Fenwick2DStatic() = default;
Fenwick2DStatic(const vector<pair<int,int>>& pts) {
xs.reserve(pts.size());
for (auto &p : pts) xs.push_back(p.first);
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
int nx = (int)xs.size();
bit.assign(nx + 1, {});
for (auto &p : pts) {
int x = p.first, y = p.second;
int r = (int)(lower_bound(xs.begin(), xs.end(), x) - xs.begin()) + 1;
for (int i = r; i <= nx; i += i & -i) bit[i].push_back(y);
}
for (int i = 1; i <= nx; ++i) {
auto &v = bit[i];
sort(v.begin(), v.end());
}
}
long long pref(int X, int Y) const {
int r = (int)(upper_bound(xs.begin(), xs.end(), X) - xs.begin());
long long ans = 0;
for (int i = r; i > 0; i -= i & -i) {
const auto &v = bit[i];
ans += upper_bound(v.begin(), v.end(), Y) - v.begin();
}
return ans;
}
long long rect(int x1, int x2, int y1, int y2) const {
if (x1 > x2 || y1 > y2) return 0;
long long a = pref(x2, y2);
long long b = pref(x1 - 1, y2);
long long c = pref(x2, y1 - 1);
long long d = pref(x1 - 1, y1 - 1);
return a - b - c + d;
}
};
static inline long long keyPoint(int x, int y) {
return ( (long long)(x + 1000000000) << 32 ) ^ (unsigned int)(y + 1000000000);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
cin >> N >> Q;
vector<pair<int,int>> pts(N);
unordered_map<int, vector<int>> xToYs;
unordered_map<int, vector<int>> yToXs;
xToYs.reserve(N * 2 + 7);
yToXs.reserve(N * 2 + 7);
unordered_set<long long> pointSet;
pointSet.reserve(N * 2 + 7);
for (int i = 0; i < N; ++i) {
int x, y;
cin >> x >> y;
pts[i] = {x, y};
xToYs[x].push_back(y);
yToXs[y].push_back(x);
pointSet.insert(keyPoint(x, y));
}
for (auto &kv : xToYs) sort(kv.second.begin(), kv.second.end());
for (auto &kv : yToXs) sort(kv.second.begin(), kv.second.end());
Fenwick2DStatic fw(pts);
auto countOnVertical = [&](int x, int y1, int y2) -> long long {
auto it = xToYs.find(x);
if (it == xToYs.end()) return 0;
const auto &v = it->second;
return upper_bound(v.begin(), v.end(), y2) - lower_bound(v.begin(), v.end(), y1);
};
auto countOnHorizontal = [&](int y, int x1, int x2) -> long long {
auto it = yToXs.find(y);
if (it == yToXs.end()) return 0;
const auto &v = it->second;
return upper_bound(v.begin(), v.end(), x2) - lower_bound(v.begin(), v.end(), x1);
};
for (int qi = 0; qi < Q; ++qi) {
int m;
cin >> m;
vector<int> x(m), y(m);
for (int i = 0; i < m; ++i) cin >> x[i] >> y[i];
// 1) Main count via half-open x-slabs [x_t, x_{t+1})
// This counts all interior points and all boundary points except
// those lying on vertical edges whose interior side is to the left.
vector<int> ux = x;
sort(ux.begin(), ux.end());
ux.erase(unique(ux.begin(), ux.end()), ux.end());
long long total = 0;
for (int t = 0; t + 1 < (int)ux.size(); ++t) {
int xl = ux[t], xr = ux[t + 1];
int xL = xl;
int xR = xr - 1;
if (xL > xR) continue;
double xmid = (xl + xr) * 0.5;
vector<int> ys;
ys.reserve(m);
for (int i = 0; i < m; ++i) {
int j = (i + 1 == m ? 0 : i + 1);
if (y[i] == y[j]) { // horizontal edge
int xa = x[i], xb = x[j];
if ((xa < xmid && xmid < xb) || (xb < xmid && xmid < xa)) {
ys.push_back(y[i]);
}
}
}
sort(ys.begin(), ys.end());
for (int i = 0; i + 1 < (int)ys.size(); i += 2) {
int y1 = ys[i], y2 = ys[i + 1];
total += fw.rect(xL, xR, y1, y2);
}
}
// 2) Add missing points on downward vertical edges (interior on the left).
for (int i = 0; i < m; ++i) {
int j = (i + 1 == m ? 0 : i + 1);
if (x[i] == x[j] && y[j] < y[i]) {
total += countOnVertical(x[i], y[j], y[i]);
}
}
cout << total << '\n';
}
return 0;
}
HackerRank Geometry – Polygon