2907-escape-polygon

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "0.5" id: 2907 name: "Escape, Polygon!" slug: "escape-polygon" timelimit: 1.0 memlimit: 256 difficultyLevelId: D author: "Vinicius Reis (Brasil)" origin: "Beecrowd" description: 'Encontre o número de combinações de três lados de um polígono convexo que fecham perfeitamente um triângulo.' editorial: | Para três lados não formarem um triângulo bloqueador (ou seja, o polígono "escapa"), os três vetores diretores dos lados devem apontar para direções que cabem dentro de um semicírculo. O total de combinações possíveis de três lados é C(N, 3). Subtraímos dessa quantidade as combinações que não formam um triângulo. Com a técnica de Two Pointers, fixamos um lado i e avançamos o ponteiro j enquanto o produto vetorial cross(V_i, V_j) for >= 0, indicando que j ainda está no mesmo semicírculo CCW que i. Se a quantidade de arestas à frente for cnt, haverá C(cnt, 2) formas de escolher duas arestas e formar um trio inválido que inicia em i. successmsg: 'Geometria + Two Pointers. Muito elegante! Evitar a simulação O(N^3) usando o complemento combinatório foi brilhante.' timeComplexity: O(N) skills: - geometry - two-pointers-array - math-computing statements: - id: a-escape testScenarioLevel: A thematicSkills: - skill: geometry points: 2 - skill: math-computing points: 1 testScenarios: - id: a-performance name: Polígonos Enormes description: "N próximo a 100.000." helpTip: "Você não passará iterando N^3 ou N^2. O Two-pointers é linear O(N)." level: A testType: PERFORMANCE skills: - skill: two-pointers-array points: 1 - id: b-fuzzing name: Fuzzing Aleatório description: "Polígonos convexos gerados aleatoriamente." helpTip: "Atenção ao overflow das operações de combinatória." level: B testType: TDD skills: - skill: math-computing points: 1 - id: c-edge name: Casos Extremos e Quadriláteros description: "Retângulos, triângulos e quadrados que forçam contagens pequenas." helpTip: "Garante que o produto vetorial igual a 0 é processado corretamente (lados paralelos)." level: C testType: TDD skills: - skill: geometry points: 1 - id: d-sample name: Exemplos do Enunciado description: "Casos simples." helpTip: "Passe nos exemplos (Retângulo = 0, Triângulo = 1)." level: D testType: TDD skills: - skill: basic-io points: 1 solutions: - id: a-otima-basica name: Two Pointers + Combinatória description: Tempo linear usando Sliding Window sobre o Produto Vetorial level: A implementations: - language: cpp paradigm: Imperative main: escape.cpp filenames: - escape.cpp - language: py paradigm: Imperative main: escape.py filenames: - escape.py - language: java paradigm: OO main: EscapePolygon filenames: - EscapePolygon.java authorSlugProblem: Unknown defaultStatement: a-escape