| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 295947 | oolimry | Vision Program (IOI19_vision) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
using namespace std;
typedef pair<int,int> ii;
vector<ii> ans;
ii Last(){
if(ans.empty()) return ii(0,0);
else return ans.back();
}
void connectChain(vector<ii> &points){
bool updown = true;
sort(all(points));
int n = sz(points);
for(int i = 1;i < n;i++){
ii a = points[i-1], b = points[i];
if(updown){
ans.push_back(ii(a.first, b.second));
}
else{
ans.push_back(ii(b.first, a.second));
}
updown = !updown;
}
ans.push_back(points.back());
}
set<ii> byX;
set<ii> byY;
void del(int x, int y){
if(byX.find(ii(x,y)) != byX.end()){
byX.erase(ii(x,y));
byY.erase(ii(y,-x));
}
}
void del(ii p){ del(p.first, p.second); }
struct box{
ii T, R, B, L;
};
ii Top(){
auto it = byY.end(); it--;
int x = -it->second, y = it->first;
return ii(x, y);
}
ii Right(){
auto it = byX.end(); it--;
int x = it->first, y = it->second;
return ii(x, y);
}
ii Bottom(){
auto it = byY.begin();
int x = -it->second, y = it->first;
return ii(x, y);
}
ii Left(){
auto it = byX.begin();
int x = it->first, y = it->second;
return ii(x, y);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
vector<box> spiral;
vector<ii> chaindown;
vector<ii> chainup;
int n; cin >> n;
for(int i = 0;i < n;i++){
int x, y; cin >> x >> y;
byX.insert(ii(x, y));
byY.insert(ii(y, -x));
}
int rem = 0;
while(sz(byX) > 0){
ii T = Top(), R = Right(), B = Bottom(), L = Left();
if(sz(byX) == 1){
chainup.push_back(T);
break;
}
if(T == R){
chainup.push_back(T);
del(T);
}
else if(T == L){
chaindown.push_back(T);
del(T);
}
else if(B == R){
chaindown.push_back(B);
del(B);
}
else if(B == L){
chainup.push_back(B);
del(B);
}
else{
del(T);
del(R);
del(B);
del(L);
spiral.push_back({T,R,B,L});
}
}
reverse(all(spiral));
if(!spiral.empty()){
ans.push_back(ii(spiral[0].L.first, 0));
for(int i = 0;i < sz(spiral);i++){
box S = spiral[i];
ii T = S.T, R = S.R, B = S.B, L = S.L;
ii cur = Last();
assert(cur.first == L.first);
if(L.second > cur.second){ ///go up first
ans.push_back(ii(L.first, T.second));
ans.push_back(ii(R.first, T.second));
ans.push_back(ii(R.first, B.second));
}
else{ ///go down first
ans.push_back(ii(L.first, B.second));
ans.push_back(ii(R.first, B.second));
ans.push_back(ii(R.first, T.second));
}
if(i != sz(spiral)-1){
int curY = ans.back().second;
ii nxtL = spiral[i+1].L;
ans.push_back(ii(nxtL.first, curY));
}
else{
int curY = ans.back().second;
ans.push_back(ii(min(B.first, T.first), curY));
}
}
}
sort(all(chainup));
sort(all(chaindown));
if(!chainup.empty()){
ii last = Last();
ii nxt = chainup[0];
ans.push_back(ii(nxt.first, last.second));
ans.push_back(ii(nxt.first, nxt.second));
connectChain(chainup);
}
if(!chaindown.empty()){
ii last = Last();
ii nxt = chaindown[0];
ans.push_back(ii(nxt.first, last.second));
ans.push_back(ii(nxt.first, nxt.second));
connectChain(chaindown);
}
cout << sz(ans) << "\n";
cerr << sz(ans) << "\n\n";
for(ii x : ans){
cout << x.first << " " << x.second << "\n";
}
for(int i = 1;i < sz(ans);i++){
ii a = ans[i-1], b = ans[i];
//cerr << a.first << " " << a.second << " " << b.first << " " << b.second << " " << i << "\n";
assert(a.first == b.first || a.second == b.second);
}
//*
//for(ii x : chainup) cerr << x.first << " " << x.second << "U\n";
//for(ii x : chaindown) cerr << x.first << " " << x.second << "D\n";
//*/
}