History: 알고리즘 대회에 필요한 기하

기하 (Geometry)

Geometry in PS

  • 기하문제란 무엇인가?

  • 기하문제는 왜 어려운가?

    • 구현이 더럽다.
    • 예외 케이스가 많다.
    • 수학적인 지식을 많이 필요로 하는 경우가 있다.

  • 기하문제를 왜 풀어야하는가?

    • 남들이 못푸니까 풀면 확실히 메리트가 있다.
    • 리저널 대회에서 유명한 기하 문제들이 그대로 나오는 경우들도 많다. (예를 들면 치킨집이라거나...)
    • 생각보다 쉬운 기하문제들도 많다.

기하문제 분류

  • 순수 기하문제 (수학)

    • delaunay triangulation
    • voronoi diagram
    • boolean operations on polygons

  • 복잡한 자료구조를 필요로 하는 기하문제

    • k-d tree

  • 해결 과정에서 기하 라이브러리가 필요한 문제

    • 기하 라이브러리가 있어야 그래프를 만들 수 있는 문제

라이브러리에 있으면 좋을 것들?

  • 기본적인 구조체

    • Point
    • Line (Segment)
    • Circle
    • Polygon
    • Plane (2-d, 3-d, 구면, cylinder, cone, ...)

  • Basic Methods

    • area, ccw
    • intersection (point, line, circle, polygon 사이의..)
    • boolean operations on polygons
    • closest pair of points

  • Advanced Methods

    • polygon triangulation
    • delaunay triangulation
    • voronoi diagram
    • shortest path (with obstacles...)

링크