#! /usr/bin/env python3 # 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. n = int(input()) min_x, max_x, min_y, max_y = 0, 0, 0, 0 cur_x, cur_y = 0, 0 for i in range(n): [tamanho, direcao] = input().split() tamanho = int(tamanho) direcao = direcao[0] # atualiza posicao atual if direcao == 'N': cur_y += tamanho elif direcao == 'S': cur_y -= tamanho elif direcao == 'L': cur_x += tamanho else: cur_x -= tamanho # 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) # adiciona 1 de cada lado pra ficar a 1 de distancia resp = 2 * (max_x - min_x + 2) + 2 * (max_y - min_y + 2) print(resp)