#include <iostream>
#include <set>
#include <math.h>
#include <algorithm>
#include <functional>
#include <iterator>
long double abss(long double x)
{
if (x < 0)
return -x;
else
return x;
}
long double sqr(long double x)
{
return x * x;
}
struct compare {
bool operator() (const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) const {
if (lhs.first != rhs.first)
return lhs.first > rhs.first;
else
return lhs.second < rhs.second;
}
};
struct circle
{
int x, y, r;
};
circle circles[300010];
void firstSubtask(int n)
{
std::set< std::pair<int, int>, compare > set;
int visited[300010] = { 0 };
int x[300010], y[300010], r[300010];
for (int i = 1; i <= n; ++i)
{
std::cin >> x[i] >> y[i] >> r[i];
set.insert(std::make_pair(r[i], i));
}
while (set.empty() == false)
{
std::pair<int, int> p = *set.begin();
set.erase(set.begin());
int xs = x[p.second], ys = y[p.second], rs = r[p.second];
visited[p.second] = p.second;
for (auto it = set.begin(); it != set.end();)
{
std::pair<int, int> sec = *it;
int xq = x[sec.second], yq = y[sec.second], rq = r[sec.second];
long double dist = sqrt(sqr(xq * 1.0 - xs * 1.0) + sqr(yq * 1.0 - ys * 1.0));
// std::cout << p.second << " " << sec.second << " " << dist << " " << rq * 1.0 + rs * 1.0 << "\n";
if (dist <= rq * 1.0 + rs * 1.0)
{
visited[sec.second] = p.second;
it = set.erase(it);
}
else
{
++it;
}
}
}
for (int i = 1; i <= n; ++i)
{
std::cout << visited[i] << " ";
}
}
void secondSubtask(int n)
{
std::set< std::pair<int, int>, compare > radiuses;
std::set< std::pair<int, int> > right, left;
for (int i = 1; i <= n; ++i)
{
radiuses.insert(std::make_pair(circles[i].r, i));
right.insert(std::make_pair(circles[i].x + circles[i].r, i));
left.insert(std::make_pair(circles[i].x - circles[i].r, i));
}
int visited[300010] = { 0 };
while (radiuses.empty() == false)
{
auto radius = radiuses.begin();
std::pair<int, int> boss = *radius;
radiuses.erase(radius);
visited[boss.second] = boss.second;
auto it = right.find(std::make_pair(circles[boss.second].x + circles[boss.second].r, boss.second));
int leftCheck = circles[boss.second].x - circles[boss.second].r;
int rightCheck = circles[boss.second].x + circles[boss.second].r;
while (it != right.begin())
{
--it;
std::pair<int, int> under = *it;
// std::cout << boss.second << " " << boss.first << " " << under.first << " " << under.second << " " << leftCheck << "\n";
if (under.first >= leftCheck)
{
it = right.erase(it);
left.erase(std::make_pair(circles[under.second].x - circles[under.second].r, under.second));
visited[under.second] = boss.second;
radiuses.erase(std::make_pair(circles[under.second].r, under.second));
}
else
break;
}
right.erase(std::make_pair(circles[boss.second].x + circles[boss.second].r, boss.second));
it = left.find(std::make_pair(circles[boss.second].x - circles[boss.second].r, boss.second));
++it;
while (it != left.end())
{
std::pair<int, int> under = *it;
// std::cout << boss.second << " " << boss.first << " " << under.first << " " << under.second << " " << rightCheck << "\n";
if (under.first <= rightCheck)
{
it = left.erase(it);
right.erase(std::make_pair(circles[under.second].x + circles[under.second].r, under.second));
visited[under.second] = boss.second;
radiuses.erase(std::make_pair(circles[under.second].r, under.second));
}
else
break;
}
left.erase(left.find(std::make_pair(circles[boss.second].x - circles[boss.second].r, boss.second)));
}
for (int i = 1; i <= n; ++i)
{
std::cout << visited[i] << " ";
}
}
void thirdSubtask(int n)
{
std::set< std::pair<int, int>, compare > radiuses;
std::set< std::pair<int, int> > xses, yses;
int visited[300010] = { 0 };
for (int i = 1; i <= n; ++i)
{
radiuses.insert(std::make_pair(circles[i].r, i));
xses.insert(std::make_pair(circles[i].x, i));
yses.insert(std::make_pair(circles[i].y, i));
}
while (radiuses.empty() == false)
{
auto radius = radiuses.begin();
std::pair<int, int> boss = *radius;
radiuses.erase(radius);
visited[boss.second] = boss.second;
auto it = xses.find(std::make_pair(circles[boss.second].x, boss.second));
if (it != xses.begin)
{
--it;
std::pair<int, int> next = *it;
long double dist = sqrt(sqr(circles[boss.second].x - circles[next.second].x) + sqr(circles[boss.second].y - circles[next.second].y));
if (dist <= circles[boss.second].r + circles[next.second].r)
{
visited[next.second] = boss.second;
radiuses.erase(std::make_pair(circles[next.second].r, next.second));
xses.erase(it);
yses.erase(std::make_pair(circles[next.second].y, next.second));
}
}
auto it = xses.find(std::make_pair(circles[boss.second].x, boss.second));
if (it != xses.end())
{
++it;
std::pair<int, int> next = *it;
long double dist = sqrt(sqr(circles[boss.second].x - circles[next.second].x) + sqr(circles[boss.second].y - circles[next.second].y));
if (dist <= circles[boss.second].r + circles[next.second].r)
{
visited[next.second] = boss.second;
radiuses.erase(std::make_pair(circles[next.second].r, next.second));
xses.erase(it);
yses.erase(std::make_pair(circles[next.second].y, next.second));
}
}
xses.erase(std::make_pair(circles[boss.second].x, boss.second));
auto it = yses.find(std::make_pair(circles[boss.second].y, boss.second));
if (it != yses.begin())
{
--it;
std::pair<int, int> next = *it;
long double dist = sqrt(sqr(circles[boss.second].x - circles[next.second].x) + sqr(circles[boss.second].y - circles[next.second].y));
if (dist <= circles[boss.second].r + circles[next.second].r)
{
visited[next.second] = boss.second;
radiuses.erase(std::make_pair(circles[next.second].r, next.second));
yses.erase(it);
xses.erase(std::make_pair(circles[next.second].x, next.second));
}
}
auto it = yses.find(std::make_pair(circles[boss.second].y, boss.second));
if (it != yses.end())
{
++it;
std::pair<int, int> next = *it;
long double dist = sqrt(sqr(circles[boss.second].x - circles[next.second].x) + sqr(circles[boss.second].y - circles[next.second].y));
if (dist <= circles[boss.second].r + circles[next.second].r)
{
visited[next.second] = boss.second;
radiuses.erase(std::make_pair(circles[next.second].r, next.second));
yses.erase(it);
xses.erase(std::make_pair(circles[next.second].x, next.second));
}
}
yses.erase(std::make_pair(circles[boss.second].y, boss.second));
}
for (int i = 1, i <= n; ++i)
{
std::cout << visited[i] << " ";
}
}
int main()
{
int n;
std::cin >> n;
if (n <= 5000)
{
firstSubtask(n);
return 0;
}
bool flag = true;
for (int i = 1; i <= n; ++i)
{
std::cin >> circles[i].x >> circles[i].y >> circles[i].r;
if (circles[i].y != 0)
{
flag = false;
}
}
if (flag)
{
secondSubtask(n);
return 0;
}
thirdSubtask(n);
}
Compilation message
circle_selection.cpp: In function 'void thirdSubtask(int)':
circle_selection.cpp:175:16: error: invalid use of non-static member function 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::begin() const [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree_const_iterator<std::pair<int, int> >]'
if (it != xses.begin)
~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/7/set:61:0,
from circle_selection.cpp:2:
/usr/include/c++/7/bits/stl_set.h:334:7: note: declared here
begin() const _GLIBCXX_NOEXCEPT
^~~~~
circle_selection.cpp:190:14: error: conflicting declaration 'auto it'
auto it = xses.find(std::make_pair(circles[boss.second].x, boss.second));
^~
circle_selection.cpp:174:14: note: previous declaration as 'std::_Rb_tree_const_iterator<std::pair<int, int> > it'
auto it = xses.find(std::make_pair(circles[boss.second].x, boss.second));
^~
circle_selection.cpp:207:14: error: conflicting declaration 'auto it'
auto it = yses.find(std::make_pair(circles[boss.second].y, boss.second));
^~
circle_selection.cpp:174:14: note: previous declaration as 'std::_Rb_tree_const_iterator<std::pair<int, int> > it'
auto it = xses.find(std::make_pair(circles[boss.second].x, boss.second));
^~
circle_selection.cpp:223:14: error: conflicting declaration 'auto it'
auto it = yses.find(std::make_pair(circles[boss.second].y, boss.second));
^~
circle_selection.cpp:174:14: note: previous declaration as 'std::_Rb_tree_const_iterator<std::pair<int, int> > it'
auto it = xses.find(std::make_pair(circles[boss.second].x, boss.second));
^~
circle_selection.cpp:242:23: error: expected ';' before '<=' token
for (int i = 1, i <= n; ++i)
^~
circle_selection.cpp:242:23: error: expected primary-expression before '<=' token
