// OBI 2023 - Fase 2 // Corrida - Solução O(N) // Mateus Bezrutchka // // Definimos que um caminho fechado com arestas paralelas aos eixos tem um // "buraco" se existe uma reta paralela a um dos eixos que entra e sai do // caminho mais de uma vez. (Formalmente, caminhos sem buraco são chamados // de Ortogonalmente Convexos.) // // Considere os seguintes fatos sobre a cerca: // - Ela precisa ser um caminho fechado. // - Ela não pode ter auto-interseção (evidente pelo requerimento de distância). // - Ela não pode ter buraco -- suponha que tivesse; então, poderíamos diminuir // o comprimento da cerca seguindo reto ao invés de "entrar" no buraco (veja // o exemplo 2 do enunciado). // Portanto, a cerca é um polígono ortogonalmente convexo. (Obs. 1) // // Agora, observe que o perímetro de um polígono ortogonalmente convexo (como // por exemplo a "escadinha" da subtarefa 2) é equivalente ao do menor retângulo // que contém ele (podemos associar cada aresta do polígono com uma região no // perímetro desse retângulo -- veja os exemplos para a subtarefa 2). (Obs. 2) // // Juntas, as observações 1 e 2 levam à conclusão de que basta calcular o // perímetro do menor retângulo que contém o caminho da corrida (considerando // também as bordas). Podemos fazer isso guardando nossa posição atual no // mapa durante o trajeto, e guardando as coordenadas minimas e maximas que // ja passamos. // #include #include using namespace std; int n; int max_x, min_x, max_y, min_y; int cur_x, cur_y; void move(int tam, char dir) { // atualiza posicao atual if (dir == 'N') cur_y += tam; else if (dir == 'S') cur_y -= tam; else if (dir == 'L') cur_x += tam; else cur_x -= tam; // atualiza maximos e minimos vistos max_x = max(max_x, cur_x); min_x = min(min_x, cur_x); max_y = max(max_y, cur_y); min_y = min(min_y, cur_y); } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { int tam; char dir; scanf(" %d %c", &tam, &dir); move(tam, dir); } // adiciona 1 de cada lado pra ficar a 1 de distancia int resp = 2 * (max_x - min_x + 2) + 2 * (max_y - min_y + 2); printf("%d\n", resp); return 0; }