| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 772096 | 2023-07-03T15:55:56 Z | davitmarg | Circle selection (APIO18_circle_selection) | C++17 | 0 ms | 0 KB |
/*
DavitMarg
In pr honky-tonk,
Down in Mexico
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <random>
#include <chrono>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 500005;
#define circle pair<pair<LL, LL>, pair<LL, int>>
#define X first.first
#define Y first.second
#define R second.first
#define I second.second
int n;
circle p[N];
LL rad;
vector<circle> g[N];
int ans[N];
bool intersect(circle a, circle b)
{
LL dx = a.X - b.X;
LL dy = a.Y - b.Y;
return (dx * dx) + (dy * dy) <= (a.R + b.R) * (a.R + b.R);
}
LL prm = 271;
LL H(pair<LL, LL> xy)
{
return ((prm * xy.first) + xy.second) % (N - 100);
}
void changeScale()
{
g.clear();
for (int i = 1; i <= n; i++)
g[H(MP(p[i].X / rad, p[i].Y / rad))].push_back(p[i]);
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> p[i].X >> p[i].Y >> p[i].R;
p[i].X += mod;
p[i].Y += mod;
p[i].I = i;
rad = max(rad, p[i].R);
}
int cur = 0;
sort(p + 1, p + 1 + n, [](circle a, circle b) {
if(a.R != b.R)
return a.R > b.R;
return a.I < b.I;
});
changeScale();
for (int i = 1; i <= n; i++)
{
if (ans[p[i].I])
continue;
if (p[i].R * 2 < rad)
{
while (p[i].R * 2 < rad)
rad /= 2;
changeScale();
}
LL x = p[i].X / rad;
LL y = p[i].Y / rad;
for(int kx = x - 2; kx <= x + 2; kx++)
for (int ky = y - 2; ky <= y + 2; ky++)
{
if (g.find(H(MP(kx, ky))) == g.end())
continue;
vector<circle>& c = g[H(MP(kx, ky))];
for (int j = 0; j < c.size(); j++)
{
if (ans[c[j].I])
continue;
if(intersect(p[i], c[j]))
ans[c[j].I] = p[i].I;
}
}
}
for (int i = 1; i <= n; i++)
cout << ans[i] << " ";
cout << endl;
}
int main()
{
fastIO;
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
/*
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/