#include #include #include #include using namespace std; class Matrix { public: vector> inputs; vector> volcanoes; vector empty; //vztahuje se k volcanoes long long int x_max, x_min, y_max, y_min; long long int x_neg, y_neg; int getInputs() { unsigned long long int in = 0; long long int x = 0, y = 0; cin >> in; if(in == 0) return 0; inputs.resize(in); for(unsigned long long int i = 0; i < in; i++) { cin >> x >> y; if(i == 0) { x_min = x; x_max = x; } setNewMinMax(x, y); inputs[i] = make_pair(x, y); } if( x_min < 0 ) x_neg = abs(x_min); else x_neg = 0; if( y_min < 0 ) y_neg = abs(y_min); else y_neg = 0; return 1; } void fillVolcanoes() { volcanoes.resize((x_max + x_neg + 1), make_pair(0, 0)); empty.resize((x_max + x_neg + 1), true); //pro kazdy vstup for( auto elem: inputs ) { long long int x = elem.first; long long int y = elem.second; //kdyz je prvni vstup pro urcite x if( empty[x] ) { volcanoes[x].first = y; volcanoes[x].second = y; empty[x] = false; continue; } if( y < volcanoes[x].first ) volcanoes[x].first = y; if( y > volcanoes[x].second ) volcanoes[x].second = y; } } int pathLength() { long long int start_x = x_min + x_neg; long long int end_x = x_max + x_neg; long long int prev_y = volcanoes[start_x].first; long long int dist = 0; for( long long int i = start_x; i <= end_x; i++ ) { long long int min = volcanoes[i].first; long long int max = volcanoes[i].second; //prechod na vyssi x dist ++; if( empty[i] ) continue; if( prev_y <= min ){ dist += distance(prev_y, max); prev_y = max; continue; } if( prev_y > min ) { dist += distance(prev_y, min); prev_y = min; continue; } if( distance(prev_y, min) <= distance( prev_y, max ) ) { dist += distance(prev_y, min); dist += distance(min, max); prev_y = max; continue; } if(distance( prev_y, max ) < distance( prev_y, min ) ) { dist += distance(prev_y, max); dist += distance(max, min); prev_y = min; continue; } cout << dist << endl; int tmp; cin >> tmp; } return dist - 1; } int distance( long long int x, long long int y ) { if( x > y ) return x - y; return y -x; } void setNewMinMax(long long int x, long long int y) { if( x > x_max ) x_max = x; if( x < x_min ) x_min = x; } //TODO: smazat void print(){ for( auto elem: inputs ) { cout << elem.first << " " << elem.second << endl; } cout << "X: " << x_min << " - " << x_max << endl; cout << "Volcanoes" << endl; for( auto elem: volcanoes ) { cout << elem.first << " " << elem.second << endl; } } }; int main() { Matrix matrix; if(matrix.getInputs() == 0 ) return 0; matrix.fillVolcanoes(); //matrix.print(); cout << matrix.pathLength() << endl; return 0; }