#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "circlesec"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
/**
Cho n đường tròn, đường tròn thứ i: có tâm (xi, yi) và bán kính ri.
Ta có 1 thuật toán:
- Tìm đường tròn có bán kính lớn nhất.
- Xóa đường tròn đó và những đường tròn giao với nó.
- Lặp lại bước 1 và 2 cho đến khi không còn đường tròn nào.
Ta gọi đường tròn i bị loại bởi đường tròn j nếu như khi đường tròn j bị loại ở bước 1 thì đường tròn i sẽ bị loại ở bước 2.
subtask 1: n <= 5000. O(N^2)
subtask 2: n <= 3e5. yi = 0, bài toán đưa về khoảng. Giả sử cho n đoạn [li, ri], ta sẽ xóa đoạn lớn nhất xong tìm những thằng
giao với đoạn đó và loại nó ra.
Subtask này đơn giản ta sweep qua các đoạn, với mỗi đoạn.
Ta lưu 3 cái set. Mỗi set sẽ sort theo 1 thông số li, ri, và radius.
Ta có nhận xét là những đoạn có l nằm trong [l, r] sẽ bị xóa xổ ở cả 3. Khi này, độ phức tạp chỉ là O(N log N) khi mỗi phần
tử chỉ được xóa 1 lần.
subtask 3: n <= 3e5, mỗi đường tròn chỉ giao với 1 đường tròn khác.
2 đường tròn giao nhau khi d(O1, O2) <= R1 + R2.
subtask 4: n <= 3e5, mỗi đường tròn có cùng bán kính.
**/
const int MAXN = 5e5 + 9;
struct Circle{
int x, y, r, id;
Circle(int _x = 0, int _y = 0, int _r = 0, int _id = 0): x(_x), y(_y), r(_r), id(_id) {}
bool operator * (const Circle &other){
return (x - other.x) * (x - other.x) + (y - other.y) * (y - other.y) <= (r + other.r) * (r + other.r);
}
} circle[MAXN];
int n;
bool deleted[MAXN];
int answer[MAXN];
namespace subtask1{
bool check(){
return n <= 5000;
}
void solve(){
memset(deleted, 0, sizeof(deleted));
FOR(i, 1, n){
int delId = 0, maxR = 0;
FOR(j, 1, n){
if (deleted[j]) continue;
if (maximize(maxR, circle[j].r)) delId = j;
}
// cout << delId << endl;
FOR(j, 1, n){
if (!deleted[j] and circle[delId] * circle[j]) {
deleted[j] = true;
answer[j] = delId;
// cout << j << ' ';
}
}
// cout << endl;
}
FOR(i, 1, n){
cout << answer[i] << ' ';
}
cout << endl;
}
}
namespace subtask2{
bool check(){
FOR(i,1 , n){
if (circle[i].y != 0) return false;
}
return n <= 300000;
}
struct cmp1{
bool operator () (const Circle &a, const Circle &b) const{
if (a.x == b.x) {
if (a.y == b.y) {
if (a.r == b.r) return a.id < b.id;
return a.r < b.r;
}
return a.y < b.y;
}
return a.x < b.x;
}
};
struct cmp2{
bool operator () (const Circle &a, const Circle &b) const{
if (a.y == b.y) {
if (a.x == b.x) {
if (a.r == b.r) return a.id < b.id;
return a.r < b.r;
}
return a.x < b.x;
}
return a.y < b.y;
}
};
struct cmp3{
bool operator () (const Circle &a, const Circle &b) const{
if (a.r == b.r) {
if (a.id == b.id) {
if (a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
return a.id > b.id;
}
return a.r < b.r;
}
};
set<Circle, cmp1> sortX;
set<Circle, cmp2> sortY;
set<Circle, cmp3> sortR;
void solve(){
FOR(i, 1, n){
int x = circle[i].x;
circle[i].x = x - circle[i].r;
circle[i].y = x + circle[i].r;
// cout << circle[i].x << ' ' << circle[i].y << ' ' << circle[i].r << endl;
sortX.insert(circle[i]);
sortY.insert(circle[i]);
sortR.insert(circle[i]);
}
vector<Circle> eraseList;
while (sortR.size() > 0){
eraseList.clear();
Circle ToErase = *sortR.rbegin();
int L = ToErase.x;
int R = ToErase.y;
// cerr << ToErase.id << ' ' << endl;
auto s1 = sortX.lower_bound(Circle(L, -inf, -inf, -inf));
while(s1 != sortX.end() and (*s1).x <= R){
eraseList.pb(*s1);
// cerr << "X: " << (*s1).x << ' ' << (*s1).id << endl;
s1++;
}
auto s2 = sortY.lower_bound(Circle(-inf, L, -inf, -inf));
while(s2 != sortY.end() and (*s2).y <= R){
// cerr << "Y: " << (*s2).y << ' ' << (*s2).id << endl;
eraseList.pb(*s2);
s2++;
}
for(auto p: eraseList){
answer[p.id] = ToErase.id;
auto it1 = sortX.find(p);
auto it2 = sortY.find(p);
auto it3 = sortR.find(p);
// cout << p.id << ' ';
if (it1 != sortX.end()) sortX.erase(it1);
if (it2 != sortY.end()) sortY.erase(it2);
if (it3 != sortR.end()) sortR.erase(it3);
}
// cout << endl;
}
FOR(i, 1, n){
cout << answer[i] << ' ';
}
cout << endl;
}
}
namespace subtask3{
bool check(){
return true;
}
struct event{
int x, id, type;
event(int _x = 0, int _id = 0, int _type = 0): x(_x), id(_id), type(_type) {}
//1: them
//2: loai bo
bool operator < (const event &other) const{
if (x == other.x){
if (type == other.type){
return id < other.id;
}
return type > other.type;
}
return x < other.x;
}
};
struct cmp{
bool operator() (const ii &a, const ii &b) const{
return (a.fi == b.fi) ? (a.se > b.se) : (a.fi < b.fi);
}
};
//moi duong tron chi giao voi toi da 1 duong tron khac.
int other[MAXN];
vector<event> events; //chua pair(x, i) la event.
multiset<ii> listY;
multiset<ii, cmp> sortR;
void solve(){
FOR(i, 1, n){
sortR.insert(ii(circle[i].r, i));
events.pb(event(circle[i].x - circle[i].r, i, 1));
// events.insert(event(circle[i].x, i, 2));
events.pb(event(circle[i].x + circle[i].r + 1, i, 2));
}
sort(events.begin(),events.end());
for(auto e: events){
if (e.type == 1) {
int addId = e.id;
listY.insert(ii(circle[addId].y, addId));
auto it = listY.lower_bound(ii(circle[addId].y, addId));
if (it != listY.end()){
auto nxt = next(it);
if (nxt != listY.end() and circle[addId] * circle[(*nxt).se]) {
other[addId] = (*nxt).se;
other[(*nxt).se] = addId;
}
}
if (it != listY.begin()){
auto prv = prev(it);
if (circle[addId] * circle[(*prv).se]) {
other[addId] = (*prv).se;
other[(*prv).se] = addId;
}
}
}
else{
int delId = e.id;
listY.erase(listY.find(ii(circle[delId].y, delId)));
}
}
while(!sortR.empty()){
auto it = *sortR.rbegin();
int id = it.se;
answer[id] = id;
// cout << circle[id].id << endl;
sortR.erase(sortR.find(it));
if (other[id] != 0) {
answer[other[id]] = id;
ii tmp = ii(circle[other[id]].r, circle[other[id]].id);
if (sortR.find(tmp) != sortR.end()) sortR.erase(sortR.find(tmp) );
}
}
// FOR(i, 1, n){
// cout << other[i] << ' ';
// }
// cout << endl;
FOR(i, 1, n){
cout << answer[i] << ' ';
}
}
}
namespace subtask4{
bool check(){
FOR(i,1 , n){
if (circle[i].r != circle[1].r) return false;
}
return true;
}
/**
Idea cua sub nay la: ta se chia
truc thanh cac o r * r.
luc nay, ta chi can xet hinh trong co tam nam trong vung hinh vuong 5r * 5r.
**/
int maxR = 0;
vector<int> listX;
int getVal(vector<int> &listVal, int x){
return lower_bound(listVal.begin(), listVal.end(), x) - listVal.begin();
}
struct cmpR{
bool operator() (const ii &a, const ii &b) const{
return (a.fi == b.fi) ? (a.se > b.se) : (a.fi < b.fi);
}
};
struct cmpGrid{
bool operator() (const ii &a, const ii &b) const{
return (a.fi == b.fi) ? (a.se < b.se) : (a.fi < b.fi);
}
};
multiset<ii, cmpR> sortR; //chua ii(r, i)
multiset<ii, cmpGrid> gridding[MAXN]; //chua ii(y, i)
vector<int> toErase;
void solve(){
maxR = circle[1].r;
FOR(i, 1, n){
sortR.insert(ii(circle[i].r, circle[i].id));
}
FOR(i, 1, n){
listX.pb(circle[i].x / maxR);
}
sort(listX.begin(), listX.end());
listX.erase(unique(listX.begin(), listX.end()), listX.end());
//
FOR(i, 1, n){
int x = getVal(listX, circle[i].x / maxR);
gridding[x].insert(ii(circle[i].y / maxR, i));
}
while(!sortR.empty()){
auto it = *sortR.rbegin();
int id = it.se;
answer[id] = id;
// cout << id << endl;
int discreteX = circle[id].x / maxR;
int discreteY = circle[id].y / maxR;
// cout << discreteX << ' ' << discreteY << endl;
FOR(nx, discreteX - 2, discreteX + 2){
int valX = getVal(listX, nx);
toErase.clear();
if (valX != listX.size() and listX[valX] == nx){
// cout << valX << ' ' << listX[valX] << ' ' << gridding[valX].size() <<endl;
auto it = gridding[valX].lower_bound(ii(discreteY - 2, -inf));
for(;it != gridding[valX].end() and (*it).fi <= discreteY + 2; it++){
int idC = (*it).se;
if (circle[idC] * circle[id]) {
answer[idC] = id;
toErase.pb(idC);
}
}
// cout << "ERASE: ";
// for(int p: toErase){
// cout << p << ' ';
// }
// cout << endl;
for(auto id: toErase){
ii t1 = ii(circle[id].r, circle[id].id);
if (sortR.find(t1) != sortR.end())
sortR.erase(sortR.find(t1));
ii t2 = ii(circle[id].y / maxR, circle[id].id);
if (gridding[valX].find(t2) != gridding[valX].end())
gridding[valX].erase(gridding[valX].find(t2));
}
}
}
}
FOR(i, 1, n){
cout << answer[i] << ' ';
}
cout << endl;
}
}
void input(){
cin >> n;
FOR(i, 1, n){
cin >> circle[i].x >> circle[i].y >> circle[i].r;
circle[i].id = i;
}
if (subtask1::check()) return subtask1::solve();
if (subtask2::check()) return subtask2::solve();
if (subtask3::check()) return subtask3::solve();
if (subtask4::check()) return subtask4::solve();
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
input();
}
/**
Warning:
Cận lmao
Code imple thiếu case nào không.
Limit.
**/
