This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pi;
typedef deque<int> di;
typedef deque<pi> dpi;
typedef deque<bool> db;
typedef vector<ll> vi;
typedef vector<pi> vpi;
typedef vector<bool> vb;
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define Yes cout << "Yes" << endl
#define endl '\n'
const ll INF = 1e9;
const int MOD = 1e9+7;
const int MAXN = 2e5;
struct circle{
ll r,ind,x,y;
};
bool compare(circle a, circle b){
if (a.r != b.r){
return a.r < b.r;
}
return a.ind < b.ind;
}
void solve()
{
ll n;
cin >> n;
vector<circle>v(n);
for (ll i = 0; i < n; i++){
ll x,y,r;
cin >> x >> y >> r;
v[i].x = x;
v[i].y = y;
v[i].ind = i;
v[i].r = r;
}
sort(all(v),compare);
/* for (int i = 0; i < n; i++){
cout << v[i].r << " ";
} */
vector<ll>rec(n,-1);
for(ll i = n-1; i >= 0; i--){
if(rec[v[i].ind] == -1){
rec[v[i].ind] = v[i].ind+1;
//int cnt = 0;
for (int j = 0; j < n; j++){
if (rec[v[j].ind] == -1 && (abs(v[j].x-v[i].x)*abs(v[j].x-v[i].x))+(abs(v[j].y-v[i].y)*abs(v[j].y-v[i].y))
<= (v[j].r+v[i].r)*(v[j].r+v[i].r)){
rec[v[j].ind] = v[i].ind+1;
//cnt++;
}
}
//cout <<"i: " << i << " cnt: " << cnt << endl;
}
}
/* vi ans(n);
for (int i = 0; i < n; i++){
ans[v[i].ind] = rec[i];
} */
for (int i = 0; i < n; i++){
cout << rec[i] << " ";
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
//To input a whole line without getting seperated by spaces, use getline(cin, string_name)
//Make string to int: stoi(your_String)
//Make int to string: to_string(your_Int)
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |