/*input
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define int long long
#define N 2015
#define bit(x,y) ((x>>y)&1LL)
#define show(x) cout << (#x) << ": " << x << endl;
#define ii pair<int,int>
ostream& operator << (ostream &os, vector<int>&x) {
for (int i = 0; i < x.size(); i++) os << x[i] << sp;
return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
cout << x.fi << sp << x.se << sp;
return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
for (int i = 0; i < x.size(); i++) os << x[i] << endl;
return os;
}
struct Circle {
int x, y, r;
Circle(int _x, int _y, int _r): x(_x), y(_y), r(_r) {};
};
struct Visitor {
int r, gate, id;
Visitor(int _r, int _gate, int _id): r(_r), gate(_gate), id(_id) {};
};
struct Event {
int r, u, v;
Event(int _r, int _u, int _v): r(_r), u(_u), v(_v) {};
};
struct dsu {
int par[N];
dsu() {
for (int i = 1; i <= N - 5; i++) par[i] = i;
}
int find(int x) {
if (par[x] == x) return x;
return par[x] = find(par[x]);
}
void uni(int x, int y) {
x = find(x); y = find(y);
if (x != y) par[x] = y;
}
} d;
bool operator < (Event x, Event y) {
return x.r < y.r;
}
bool operator < (Visitor x, Visitor y) {
return x.r < y.r;
}
int n, m;
int W, H;
vector<Circle> circle;
vector<Visitor> visitor;
vector<Event> event;
int ans[N][5];
// m, m+1, m+2, m+3 lan luot la goc duoi, phai, tren, trai cua hinh chu nhat
bool canPass(int lim, int u, int v) {
if (u >= n) {
if (v >= n) return 1;
if (u == n) return circle[v].y - circle[v].r >= 2 * lim;
if (u == n + 1) return W - (circle[v].x + circle[v].r) >= 2 * lim;
if (u == n + 2) return H - (circle[v].y + circle[v].r) >= 2 * lim;
if (u == n + 3) return circle[v].x - circle[v].r >= 2 * lim;
assert(1 == 0);
}
if (v >= n) return canPass(lim, v, u);
int dx = circle[u].x - circle[v].x;
int dy = circle[u].y - circle[v].y;
int dis = dx * dx + dy * dy;
int mdis = circle[u].r + circle[v].r + 2 * lim;
mdis *= mdis;
return dis >= mdis;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef UncleGrandpa
freopen("1test.inp", "r", stdin);
#endif
cin >> n >> m;
cin >> W >> H;
for (int i = 1; i <= n; i++) {
int x, y, z; cin >> x >> y >> z;
circle.push_back(Circle(x, y, z));
}
for (int i = 1; i <= m; i++) {
int x, y; cin >> x >> y;
visitor.push_back(Visitor(x, y, i));
}
sort(visitor.begin(), visitor.end());
for (int i = 0; i < n + 4; i++) {
for (int j = i + 1; j < n + 4; j++) {
int l = 0, r = W + H;
while (l != r) {
int mid = (l + r + 1) / 2;
if (canPass(mid, i, j)) l = mid;
else r = mid - 1;
}
event.push_back(Event(l, i, j));
}
}
sort(event.begin(), event.end());
int it = 0;
for (auto cur : visitor) {
while (it < event.size() && event[it].r < cur.r) {
d.uni(event[it].u, event[it].v);
it++;
}
int gate = cur.gate - 1;
auto con = [gate](int x, int y) {
return d.find(n + (gate + x) % 4) == d.find(n + (gate + y) % 4);
};
ans[cur.id][gate] = true;
if (!con(0, 1) && !con(0, 2) && !con(0, 3)) ans[cur.id][gate + 1] = true;
if (!con(0, 2) && !con(0, 3) && !con(1, 2)) ans[cur.id][(gate + 2) % 4] = true;
if (!con(0, 3) && !con(2, 3) && !con(1, 3)) ans[cur.id][(gate + 3) % 4] = true;
}
for (int i = 1; i <= m; i++) {
for (int j = 0; j < 4; j++) if (ans[i][j]) cout << j + 1;
cout << endl;
}
}
Compilation message
park.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<long long int>&)':
park.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < x.size(); i++) os << x[i] << sp;
^
park.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::pair<long long int, long long int> >&)':
park.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < x.size(); i++) os << x[i] << endl;
^
park.cpp: In function 'int main()':
park.cpp:150:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (it < event.size() && event[it].r < cur.r) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1149 ms |
76144 KB |
Output is correct |
| 2 |
Correct |
1129 ms |
76144 KB |
Output is correct |
| 3 |
Correct |
1069 ms |
76144 KB |
Output is correct |
| 4 |
Correct |
1119 ms |
76144 KB |
Output is correct |
| 5 |
Correct |
1073 ms |
76144 KB |
Output is correct |
| 6 |
Correct |
1119 ms |
76144 KB |
Output is correct |
| 7 |
Correct |
1056 ms |
76144 KB |
Output is correct |
| 8 |
Correct |
1002 ms |
76144 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2280 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
63 ms |
6940 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1149 ms |
76144 KB |
Output is correct |
| 2 |
Correct |
1129 ms |
76144 KB |
Output is correct |
| 3 |
Correct |
1069 ms |
76144 KB |
Output is correct |
| 4 |
Correct |
1119 ms |
76144 KB |
Output is correct |
| 5 |
Correct |
1073 ms |
76144 KB |
Output is correct |
| 6 |
Correct |
1119 ms |
76144 KB |
Output is correct |
| 7 |
Correct |
1056 ms |
76144 KB |
Output is correct |
| 8 |
Correct |
1002 ms |
76144 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2280 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2280 KB |
Output is correct |
| 11 |
Runtime error |
63 ms |
6940 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
