#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long double, int> pdi;
pii operator+(pii a, pii b) {
return pii(a.first+b.first, a.second+b.second);
}
pii operator-(pii a, pii b) {
return pii(a.first-b.first, a.second-b.second);
}
ll operator*(pii a, pii b) {
return (ll)a.first*b.second-(ll)a.second*b.first;
}
ll dot(pii a, pii b) {
return (ll)a.first*b.first+(ll)a.second*b.second;
}
ld mag(pii a) {
return sqrt(dot(a, a));
}
ld getang(pii a, pii b) { // returns cos theta*mag(b)
return dot(a, b)/mag(a)/mag(b);
}
const int MAXN = 3000; // should be 3e4
const int BLOCK = 1; // should be 100
const int MAXBLOCKS = MAXN/BLOCK;
int n, m, q;
vector<int> big_groups;
int big_inv[MAXN];
ll num[MAXBLOCKS][MAXN];
pii points[MAXN];
vector<int> in_group[MAXN];
int id[MAXN];
pii p1, p2;
vector<int> points_sorted[2][2]; // up or down, sorted by costheta of p1 or p2
int points_sorted_inv[2][MAXN]; // no reason to consider top or bottom, we are already going to know the side
vector<int> group_sort[MAXN][2][2];
int bit[MAXN];
void ins(int p, int v) {
for (; p < n; p |= (p+1)) bit[p] += v;
}
int sum(int p) {
int s = 0;
for (p++; p > 0; p &= (p-1)) s += bit[p-1];
return s;
}
pii base, comp_vec;
struct comp {
bool operator()(int a, int b) {
return getang(comp_vec, points[a]-base) < getang(comp_vec, points[b]-base);
}
} comp;
void make_num(int p, ll ans[]) {
for (int j = 0; j < 2; j++) {
if (j == 0) {
base = p1;
comp_vec = p2-p1;
}
else {
base = p2;
comp_vec = p1-p2;
}
vector<ld> updates;
int num = group_sort[p][j^1][j].size();
for (int v: group_sort[p][j^1][j]) { // iterating over points of type p on the other side sorted by the first point sweeping left to righ
updates.push_back(getang(comp_vec, base-points[v])); // negative
}
int m = points_sorted[j][j].size();
int k = 0;
for (int i = 0; i < m; i++) { // iterating over all points not of type p on this side sorted by the left point angle left to right
int cur = points_sorted[j][j][i];
if (id[cur] == p) continue;
while (k < updates.size() && updates[k] < getang(comp_vec, points[cur]-base)) k++;
ans[id[cur]] += k-num;
}
updates.clear();
base = p1+p2-base;
for (int v: group_sort[p][j^1][j^1]) { // type p, opposite side, right point, sweeping left to right
updates.push_back(getang(comp_vec, base-points[v])); // positive
}
k = 0;
for (int i = 0; i < m; i++) { // not of type p, this side, right point, sweeping left to right
int cur = points_sorted[j][j^1][i];
if (id[cur] == p) continue;
while (k < updates.size() && updates[k] < getang(comp_vec, points[cur]-base)) k++;
ans[id[cur]] += num-k;
}
fill(bit, bit+n, 0);
m = points_sorted[j][j].size();
k = 0;
updates.clear();
base = p1+p2-base;
for (int v: group_sort[p][j][j]) updates.push_back(getang(comp_vec, points[v]-base));
// updates is full of things sweeping from left to right on top with respect to left point
for (int i = 0; i < m; i++) { // sweep left to right from bottom pov, second point, on the bottom
int cur = points_sorted[j][j][i];
if (id[cur] == p) continue;
while (k < updates.size() && updates[k] < getang(comp_vec, points[cur]-base)) {
int mn = -1;
int mx = m; // which points have we passed
int v = group_sort[p][j][j][k];
ld comp_ang = getang(comp_vec, points[v]-(p1+p2-base));
while (mx > mn+1) {
int mid = (mn+mx)/2;
int mpoint = points_sorted[j][j^1][mid];
if (getang(comp_vec, points[mpoint]-(p1+p2-base)) < comp_ang) mn = mid;
else mx = mid;
}
ins(0, 1);
ins(mx, -1);
k++;
}
ans[id[cur]] += sum(points_sorted_inv[j^1][cur]);
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> points[i].first >> points[i].second >> id[i];
id[i]--;
in_group[id[i]].push_back(i);
}
cin >> p1.first >> p1.second >> p2.first >> p2.second;
for (int i = 0; i < m; i++) {
if (in_group[i].size() >= BLOCK) {
big_groups.push_back(i);
}
for (int v: in_group[i]) {
bool b = (p2-p1)*(points[v]-p1) < 0;
for (int j = 0; j < 2; j++) {
group_sort[i][b][j].push_back(v);
points_sorted[b][j].push_back(v);
}
}
base = p1;
comp_vec = p2-p1;
sort(group_sort[i][0][0].begin(), group_sort[i][0][0].end());
base = p2;
sort(group_sort[i][0][1].begin(), group_sort[i][0][1].end());
comp_vec = p1-p2;
sort(group_sort[i][1][1].begin(), group_sort[i][1][1].end());
base = p1;
sort(group_sort[i][1][0].begin(), group_sort[i][1][0].end());
}
base = p1;
comp_vec = p2-p1;
sort(points_sorted[0][0].begin(), points_sorted[0][0].end());
base = p2;
sort(points_sorted[0][1].begin(), points_sorted[0][1].end());
comp_vec = p1-p2;
sort(points_sorted[1][1].begin(), points_sorted[1][1].end());
base = p1;
sort(points_sorted[1][0].begin(), points_sorted[1][0].end());
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
for (int i = 0; i < points_sorted[j][k].size(); i++) points_sorted_inv[k][points_sorted[j][k][i]] = i;
}
}
for (int i = 0; i < big_groups.size(); i++) {
make_num(big_groups[i], num[i]);
big_inv[big_groups[i]] = i;
}
cin >> q;
for (int i = 0; i < q; i++) {
int x, y; cin >> x >> y;
x--; y--;
if (in_group[x].size() >= BLOCK) {
cout << num[big_inv[x]][y] << "\n";
}
else { // deal with this later
}
}
}
Compilation message
dragon2.cpp: In function 'void make_num(int, ll*)':
dragon2.cpp:88:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | while (k < updates.size() && updates[k] < getang(comp_vec, points[cur]-base)) k++;
| ~~^~~~~~~~~~~~~~~~
dragon2.cpp:100:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | while (k < updates.size() && updates[k] < getang(comp_vec, points[cur]-base)) k++;
| ~~^~~~~~~~~~~~~~~~
dragon2.cpp:113:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | while (k < updates.size() && updates[k] < getang(comp_vec, points[cur]-base)) {
| ~~^~~~~~~~~~~~~~~~
dragon2.cpp: In function 'int main()':
dragon2.cpp:174:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | for (int i = 0; i < points_sorted[j][k].size(); i++) points_sorted_inv[k][points_sorted[j][k][i]] = i;
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.cpp:177:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
177 | for (int i = 0; i < big_groups.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
1492 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
