#include <bits/stdc++.h>
#define pb push_back
using namespace std;
constexpr static int SIZE = 200001;
vector<int> g[SIZE];
bitset<SIZE> visited;
vector<array<int, 2>> rows[SIZE];
vector<array<int, 2>> intervals[SIZE];
vector<int> uu, vv, aa, bb;
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b)
{
uu = u;
vv = v;
aa = a;
bb = b;
}
void configure_rows(const vector<int>& x, const vector<int>& y)
{
int n = x.size();
for (int i = 0; i < n; i++)
rows[y[i]].pb({x[i], i});
for (int i = 0; i < SIZE; i+=2)
sort(rows[i].begin(), rows[i].end());
}
void configure_intervals()
{
for (int y = 0; y < SIZE; y+=2)
{
if (rows[y].empty())
continue;
intervals[y].pb({rows[y][0][0], rows[y][0][0]});
for (int i = 1; i < rows[y].size(); i++)
{
if (intervals[y].back()[1] + 2 == rows[y][i][0])
{
intervals[y].back()[1] = rows[y][i][0];
g[rows[y][i-1][1]].pb(rows[y][i][1]);
g[rows[y][i][1]].pb(rows[y][i-1][1]);
}
else
{
intervals[y].pb({rows[y][i][0], rows[y][i][0]});
}
}
}
}
// Line from a1 to a2 and line from b1 to b2
// Checking intersection (touching also counts)
bool is_intersecting(int a1, int a2, int b1, int b2)
{
return (b2 >= a1 && a1 >= b1) || (b2 >= a2 && a2 >= b1) || (a2 >= b1 && b1 >= a1) || (a2 >= b2 && b2 >= a1);
}
void configure_horizontal_connections()
{
for (int y = 2; y < SIZE; y+=2)
{
int i = 0, j = 0;
while (i < intervals[y].size() && j < intervals[y-2].size())
{
if (is_intersecting(intervals[y][i][0], intervals[y][i][1], intervals[y-2][j][0], intervals[y-2][j][1]))
{
int x = max(intervals[y][i][0], intervals[y-2][j][0]);
array<int, 2> pos = {x, 0};
int a = (*lower_bound(rows[y].begin(), rows[y].end(), pos))[1];
int b = (*lower_bound(rows[y-2].begin(), rows[y-2].end(), pos))[1];
g[a].pb(b);
g[b].pb(a);
}
if (intervals[y][i][1] > intervals[y-2][j][1])
j++;
else
i++;
}
}
}
int node_sum = 0;
void dfs(int node)
{
visited[node] = true;
node_sum++;
for (int c : g[node])
if (!visited[c])
dfs(c);
}
void build_grid(const vector<int>& xv, const vector<int>& yv)
{
vector<int> u, v, a, b;
set<array<int, 2>> fountains;
for (int y = 0; y < SIZE; y+=2)
{
for (auto [x, node] : rows[y])
{
for (int c : g[node])
{
if (yv[c] != y || xv[c] > x)
continue;
int fx = x-1, fy = y-1;
if (fountains.find({fx, fy}) != fountains.end())
fy += 2;
assert(fountains.find({fx, fy}) == fountains.end());
u.pb(node), v.pb(c), a.pb(fx), b.pb(fy);
fountains.insert({fx, fy});
}
}
for (auto [x, node] : rows[y])
{
for (int c : g[node])
{
if (yv[c] <= y)
continue;
int fx = x+1, fy = y+1;
if (fountains.find({fx, fy}) != fountains.end())
fx -= 2;
assert(fountains.find({fx, fy}) == fountains.end());
u.pb(node), v.pb(c), a.pb(fx), b.pb(fy);
fountains.insert({fx, fy});
}
}
}
build(u, v, a, b);
}
int construct_roads(vector<int> x, vector<int> y)
{
configure_rows(x, y);
configure_intervals();
configure_horizontal_connections();
dfs(0);
if (node_sum < x.size())
return 0;
else
build_grid(x, y);
return 1;
}
int main()
{
int n;
cin >> n;
vector<int> y(n), x(n);
for (int i = 0; i < n; i++)
cin >> x[i] >> y[i];
int res = construct_roads(x, y);
if (res == 1)
cout <<"YES\n";
else
cout <<"NO\n";
if (res == 1)
for (int i = 0; i < uu.size(); i++)
cout << uu[i] << "-" << vv[i] << ": " << aa[i] << " " << bb[i] << "\n";
}
Compilation message
parks.cpp: In function 'void configure_intervals()':
parks.cpp:38:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int i = 1; i < rows[y].size(); i++)
| ~~^~~~~~~~~~~~~~~~
parks.cpp: In function 'void configure_horizontal_connections()':
parks.cpp:67:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | while (i < intervals[y].size() && j < intervals[y-2].size())
| ~~^~~~~~~~~~~~~~~~~~~~~
parks.cpp:67:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | while (i < intervals[y].size() && j < intervals[y-2].size())
| ~~^~~~~~~~~~~~~~~~~~~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:143:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | if (node_sum < x.size())
| ~~~~~~~~~^~~~~~~~~~
parks.cpp: In function 'int main()':
parks.cpp:165:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
165 | for (int i = 0; i < uu.size(); i++)
| ~~^~~~~~~~~~~
/usr/bin/ld: /tmp/ccXQvm44.o: in function `build(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)':
grader.cpp:(.text+0x270): multiple definition of `build(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'; /tmp/ccQ3yGV5.o:parks.cpp:(.text+0x7b0): first defined here
/usr/bin/ld: /tmp/ccXQvm44.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccQ3yGV5.o:parks.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
