2962-arte-digital

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "0.5" id: 2962 name: "Arte Digital" slug: "arte-digital" timelimit: 1.0 memlimit: 200 difficultyLevelId: D author: "Maratona de Programação 2019, SBC Brazil" origin: "Beecrowd" description: 'Dadas as coordenadas e a área de alcance de múltiplos sensores em uma sala, determine se é possível ir de uma ponta à outra sem ser detectado.' editorial: | Para resolver este problema podemos considerar os sensores como círculos. A sala tem 4 bordas: Esquerda, Direita, Baixo e Cima. Queremos ir do canto (0,0) ao canto (M,N). Um caminho é bloqueado se existir um componente conexo de sensores que se tocam e que liga o conjunto de paredes {Esquerda, Cima} ao conjunto {Direita, Baixo}. Podemos construir um grafo onde cada sensor é um vértice e há aresta se as circunferências se interceptam. Calculamos os limites usando distância quadrática. Uma simples Busca em Profundidade (DFS) resolve em O(K^2). successmsg: 'Caminho livre! Ótima sacada de usar DFS em componentes de interseção geométrica.' timeComplexity: O(K^2) skills: - graphs - bfs-dfs - geometry statements: - id: a-arte-digital testScenarioLevel: A thematicSkills: - skill: graphs points: 2 - skill: geometry points: 1 testScenarios: - id: a-performance name: Teste de Carga Máxima description: "Casos com K=1000 onde a construção do grafo requer K^2 operações." helpTip: "Use a fórmula da distância ao quadrado para não sofrer com precisão e complexidade de raiz quadrada (sqrt)." level: A testType: PERFORMANCE skills: - skill: graphs points: 1 - id: b-fuzzing name: Fuzzing Aleatório description: "Diversas configurações aleatórias." helpTip: "Atenção ao estouro de limite da variável (use long long 64 bits para distância quadrática)." level: B testType: TDD skills: - skill: geometry points: 1 - id: c-edge name: Casos Extremos description: "K=1 bloqueando os dois lados, caminhos zigue-zague, tangências exatas." helpTip: "Verifique se você lida corretamente quando os círculos tocam os limites extamente na borda." level: C testType: TDD skills: - skill: bfs-dfs points: 1 - id: d-sample name: Exemplos do Enunciado description: "Exemplo inicial básico." helpTip: "Seu programa deve passar no exemplo antes de tentar submeter." level: D testType: TDD skills: - skill: basic-io points: 1 solutions: - id: a-otima-basica name: DFS e Grafos Implícitos O(K²) description: Verifica componentes conexos que encostam nos extremos opostos do salão. level: A implementations: - language: cpp paradigm: Imperative main: arte.cpp filenames: - arte.cpp - language: py paradigm: Imperative main: arte.py filenames: - arte.py - language: java paradigm: OO main: ArteDigital filenames: - ArteDigital.java authorSlugProblem: Unknown defaultStatement: a-arte-digital