/*
ID: awesome35
LANG: C++14
TASK: vans
*/
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353
const ld pi = 3.1415926535;
void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void build_primes(vi& primes, int size)
{
vi visited;
visited.rsz(size, 0);
FOR(i, 2, size)
{
if (visited[i] == 0)
{
primes.pb(i);
int a = i;
while (a < size)
{
visited[a] = 1;
a += i;
}
}
}
}
vector<vector<ll>> matrix_mult(vector<vector<ll>>& a, vector<vector<ll>>& b)
{
int n = a.size();
vector<vector<ll>> answer;
answer.resize(n);
for (int i = 0; i < n; i++) answer[i].resize(n, 0);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++) // calculate answer[i][j]
{
for (int k = 0; k < n; k++)
answer[i][j] = (answer[i][j] + a[i][k] * b[k][j]) % inf;
}
}
return answer;
}
int modInverse(int a, int m)
{
int m0 = m;
int y = 0, x = 1;
if (m == 1)
return 0;
while (a > 1)
{
// q is quotient
int q = a / m;
int t = m;
// m is remainder now, process same as
// Euclid's algo
m = a % m, a = t;
t = y;
// Update y and x
y = x - q * y;
x = t;
}
// Make x positive
if (x < 0)
x += m0;
return x;
}
ll power(ll x, ll y)
{
ll k = 1LL << 60;
ll z = 1;
while (k != 0)
{
z *= z;
z %= inf;
if (y >= k)
{
z *= x;
z %= inf;
y -= k;
}
k >>= 1;
}
return z;
}
struct point
{
ld x, y;
bool operator<(const point& rhs)const
{
if (x == rhs.x)return y < rhs.y;
return x < rhs.x;
}
};
struct pt
{
ll x, y;
bool operator<(const point& rhs)const
{
if (x == rhs.x)return y < rhs.y;
return x < rhs.x;
}
};
// remember that you need to take abs
long double area(point x, point y, point z)
{
return (x.y * y.x + y.y * z.x + z.y * x.x - x.x * y.y - y.x * z.y - z.x * x.y) / 2.0;
}
bool clockwise(point x, point y, point z)
{
return area(x, y, z) > 0;
}
// remember that you need to take abs
long double area(pt x, pt y, pt z)
{
return (x.y * y.x + y.y * z.x + z.y * x.x - x.x * y.y - y.x * z.y - z.x * x.y) / 2.0;
}
bool clockwise(pt x, pt y, pt z)
{
return area(x, y, z) > 0;
}
ll gcd(ll a, ll b)
{
if (a > b)swap(a, b);
if (a == 0)return b;
return gcd(a, b % a);
}
int popcount(ll a)
{
int count = 0;
while (a)
{
count += (a & 1);
a >>= 1;
}
return count;
}
ll choose(ll n, ll r)
{
ll p = 1, k = 1;
if (n - r < r)
r = n - r;
if (r != 0) {
while (r) {
p *= n;
k *= r;
long long m = gcd(p, k);
p /= m;
k /= m;
n--;
r--;
}
}
else
p = 1;
return p;
}
vll prefix_hash(string& a, vll& powers)
{
int n = sz(a);
vll prefix(n + 1);
F0R(i, n)prefix[i + 1] = (prefix[i] + powers[i] * (a[i] - 'a' + 1)) % inf;
return prefix;
}
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
//the return type was size_t. But isnt that problematic?
uint64_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
struct custom_hash_fast {
//the return type was size_t. But isnt that problematic?
uint64_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
x ^= FIXED_RANDOM;
return x ^ (x >> 16);
}
};
void setIO(string s) {
ios_base::sync_with_stdio(0); cin.tie(0);
if (sz(s))
{
freopen((s + ".in").c_str(), "r", stdin);
if (s != "test2")
freopen((s + ".out").c_str(), "w", stdout);
}
}
struct tree
{
ll x, y, r;
};
struct person
{
ll i, r, index;
bool operator<(const person& x)const
{
return r < x.r;
}
};
struct edge
{
ll i, j;
ld dist;
bool operator<(const edge& x)const
{
return dist < x.dist;
}
};
ll n, q, w, h;
vector<tree>a;
ld calc(int i, int j)
{
return sqrt((a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y)) - a[i].r - a[j].r;
}
vector<vi>ans;
vi link;
int find(int a)
{
return a == link[a] ? a : link[a] = find(link[a]);
}
void add(edge& x)
{
int i = x.i, j = x.j;
i = find(i), j = find(j);
if (i != j)
link[i] = j;
}
void solve(int i, int index)
{
int a = find(n), b = find(n + 1), c = find(n + 2), d = find(n + 3);
if (i == 0)
{
ans[index].pb(0);
if (b != a && b != d && b != c)ans[index].pb(1);
if (a != b && c != d && a != c && b != d)ans[index].pb(2);
if (a != b && a != c && a != d)ans[index].pb(3);
}
else if (i == 1)
{
if (b != a && b != c && b != d)ans[index].pb(0);
ans[index].pb(1);
if (c != b && c != a && c != d)ans[index].pb(2);
if (c != b && a != d && a != c && b != d)ans[index].pb(3);
}
else if (i == 2)
{
if (a != c && b != d && c != d && a != b)ans[index].pb(0);
if (c != b && c != a && c != d)ans[index].pb(1);
ans[index].pb(2);
if (d != c && d != b && d != a)ans[index].pb(3);
}
else
{
if (a != b && a != c && a != d)ans[index].pb(0);
if (a != c && a != d && b != d && b != c)ans[index].pb(1);
if (d != a && d != b && d != c)ans[index].pb(2);
ans[index].pb(3);
}
}
int main()
{
setIO("");
cin >> n >> q >> w >> h;
a.rsz(n);
trav(x, a)cin >> x.x >> x.y >> x.r;
vector<person>b(q);
int c = 0;
trav(x, b)cin >> x.r >> x.i, x.i--, x.index = c++;
sort(all(b));
link.rsz(n + 4);// n,n+1,n+2,n+3 are the four sides. left, down, right, up
iota(all(link), 0);
vector<edge>e;
F0R(i, n)
{
FOR(j, i + 1, n)
{
ld val = calc(i, j);
e.pb({ i,j,val });
}
}
F0R(i, n)
{
e.pb({ n,i,(ld)a[i].x - a[i].r });
e.pb({ n + 1,i,(ld)a[i].y - a[i].r });
e.pb({ n + 2,i,(ld)w - a[i].x - a[i].r });
e.pb({ n + 3,i,(ld)h - a[i].y - a[i].r });
}
sort(all(e));
ans.rsz(q);
int i = 0;
trav(x, b)
{
while (i < sz(e) && 2 * x.r > e[i].dist)
{
add(e[i++]);
}
solve(x.i, x.index);
}
F0R(i, q)
{
trav(x, ans[i])cout << x + 1;
cout << endl;
}
}
Compilation message
park.cpp: In function 'void setIO(std::string)':
park.cpp:229:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
229 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:231:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
231 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
475 ms |
66180 KB |
Output is correct |
| 2 |
Correct |
476 ms |
66388 KB |
Output is correct |
| 3 |
Correct |
472 ms |
66308 KB |
Output is correct |
| 4 |
Correct |
485 ms |
66308 KB |
Output is correct |
| 5 |
Correct |
478 ms |
66456 KB |
Output is correct |
| 6 |
Correct |
480 ms |
66336 KB |
Output is correct |
| 7 |
Correct |
467 ms |
66308 KB |
Output is correct |
| 8 |
Correct |
453 ms |
66308 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
9184 KB |
Output is correct |
| 2 |
Correct |
85 ms |
10336 KB |
Output is correct |
| 3 |
Correct |
71 ms |
10208 KB |
Output is correct |
| 4 |
Correct |
77 ms |
10208 KB |
Output is correct |
| 5 |
Correct |
75 ms |
10212 KB |
Output is correct |
| 6 |
Correct |
81 ms |
10356 KB |
Output is correct |
| 7 |
Correct |
64 ms |
9700 KB |
Output is correct |
| 8 |
Correct |
66 ms |
9700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
475 ms |
66180 KB |
Output is correct |
| 2 |
Correct |
476 ms |
66388 KB |
Output is correct |
| 3 |
Correct |
472 ms |
66308 KB |
Output is correct |
| 4 |
Correct |
485 ms |
66308 KB |
Output is correct |
| 5 |
Correct |
478 ms |
66456 KB |
Output is correct |
| 6 |
Correct |
480 ms |
66336 KB |
Output is correct |
| 7 |
Correct |
467 ms |
66308 KB |
Output is correct |
| 8 |
Correct |
453 ms |
66308 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
82 ms |
9184 KB |
Output is correct |
| 12 |
Correct |
85 ms |
10336 KB |
Output is correct |
| 13 |
Correct |
71 ms |
10208 KB |
Output is correct |
| 14 |
Correct |
77 ms |
10208 KB |
Output is correct |
| 15 |
Correct |
75 ms |
10212 KB |
Output is correct |
| 16 |
Correct |
81 ms |
10356 KB |
Output is correct |
| 17 |
Correct |
64 ms |
9700 KB |
Output is correct |
| 18 |
Correct |
66 ms |
9700 KB |
Output is correct |
| 19 |
Correct |
548 ms |
72668 KB |
Output is correct |
| 20 |
Correct |
555 ms |
72520 KB |
Output is correct |
| 21 |
Correct |
544 ms |
72616 KB |
Output is correct |
| 22 |
Correct |
534 ms |
72516 KB |
Output is correct |
| 23 |
Correct |
538 ms |
72668 KB |
Output is correct |
| 24 |
Correct |
535 ms |
72516 KB |
Output is correct |
