#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g;
vector<int> clr;
int clrs = 0;
vector<int> st;
vector<bool> inSt;
int t;
vector<int> up;
void dfs(int v){
int tin = t++;
up[v] = tin;
st.push_back(v);
inSt[v] = true;
for(int u : g[v]){
if(clr[u] == -1 && !inSt[u]){
dfs(u);
}
if(inSt[u]){
up[v] = min(up[v], up[u]);
}
}
if(up[v] == tin){
while(st.back() != v){
int u = st.back();
st.pop_back();
inSt[u] = false;
clr[u] = clrs;
}
inSt[v] = false;
clr[v] = clrs;
st.pop_back();
clrs++;
}
}
vector<pair<int, int>> points;
struct line{
int x1, y1, x2, y2;
int ind1, ind2;
line(int ind1_, int ind2_){
ind1 = ind1_;
ind2 = ind2_;
x1 = points[ind1].first;
x2 = points[ind2].first;
y1 = points[ind1].second;
y2 = points[ind2].second;
if(x1 > x2) swap(x1, x2);
if(y1 > y2) swap(y1, y2);
}
};
bool check(line hor, line vert){
return hor.x1 < vert.x1 && vert.x1 < hor.x2 && vert.y1 < hor.y1 && hor.y1 < vert.y2;
}
int vertvertices;
void preparesat(int vert_, int hor_){
g.resize((vert_ + hor_) * 2);
vertvertices = vert_;
}
int vertical(int v){
return v * 2;
}
int nvertical(int v){
return v * 2 + 1;
}
int gorizontal(int v){
return vertvertices * 2 + v * 2;
}
int ngorizontal(int v){
return vertvertices * 2 + v * 2 + 1;
}
void solve(){
int n;
cin >> n;
points.resize(n);
vector<pair<int, int>> lines(n, {-1, -1});
unordered_map<int, int> vert;
unordered_map<int, int> hor;
vector<line> vertlines;
vector<line> horlines;
for(int i = 0; i < n; i++){
int x, y;
cin >> x >> y;
points[i].first = x;
points[i].second = y;
if(vert.find(x) != vert.end()){
int j = vert[x];
lines[i].first = vertlines.size();
lines[j].first = vertlines.size();
vertlines.push_back(line(i, j));
}else{
vert[x] = i;
}
if(hor.find(y) != hor.end()){
int j = hor[y];
lines[i].second = horlines.size();
lines[j].second = horlines.size();
horlines.push_back(line(i, j));
}else{
hor[y] = i;
}
}
preparesat(vertlines.size(), horlines.size());
for(int i = 0; i < n; i++){
if(lines[i].first == -1 && lines[i].second == -1){
cout << "NE\n";
return;
}else if(lines[i].first == -1){
int v = gorizontal(lines[i].second);
g[v + 1].push_back(v);
}else if(lines[i].second == -1){
int v = vertical(lines[i].first);
g[v + 1].push_back(v);
}else{
int v = vertical(lines[i].first);
int u = gorizontal(lines[i].second);
g[u].push_back(v + 1);
g[u + 1].push_back(v);
g[v].push_back(u + 1);
g[v + 1].push_back(u);
}
}
for(int i = 0; i < horlines.size(); i++){
for(int j = 0; j < vertlines.size(); j++){
if(check(horlines[i], vertlines[j])){
int v = gorizontal(i);
int u = vertical(j);
g[v].push_back(u + 1);
g[u].push_back(v + 1);
}
}
}
int w = g.size();
inSt.assign(w, false);
clr.assign(w, -1);
up.assign(w, -1);
for(int i = 0; i < w; i++){
if(clr[i] == -1){
dfs(i);
}
}
vector<pair<int, int>> ans;
for(int i = 0; i < vertlines.size(); i++){
int v = vertical(i);
if(clr[v] == clr[v + 1]){
cout << "NE\n";
return;
}else if(clr[v] < clr[v + 1]){
ans.push_back({vertlines[i].ind1, vertlines[i].ind2});
}
}
for(int i = 0; i < horlines.size(); i++){
int v = gorizontal(i);
if(clr[v] == clr[v + 1]){
cout << "NE\n";
return;
}else if(clr[v] < clr[v + 1]){
ans.push_back({horlines[i].ind1, horlines[i].ind2});
}
}
cout << "DA\n";
for(auto [a, b] : ans){
cout << a + 1 << ' ' << b + 1 << '\n';
}
}
signed main(){
#ifdef LOCAL
freopen("D:\\projects\\olymp\\input.txt", "r", stdin);
freopen("D:\\projects\\olymp\\output.txt", "w", stdout);
#endif
int t = 1;
// cin >> t;
while(t--){
solve();
}
}
# | 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... |