28 Aug 2020

[BOJ 10254]

고속도로

문제 바로가기 : https://www.acmicpc.net/problem/10254
문제 설명은 위 링크에서 확인해주시길 바랍니다.

solution

review

Convex Hull 알고리즘으로 볼록 껍질을 구한 후, 회전하는 캘리퍼스 알고리즘을 이용하면 원하는 답을 얻을 수 있다.
stonejjun님의 글에 알고리즘 설명이 잘 돼있으니 참고!
코드에 쓰인 A, B, C, D는 위 링크에서 쓰이는 점 A, B, C, D를 의미한다.

기존에 썼던 Convex Hull 알고리즘을 가능한 건드리지 않으면서 추가했다.

Location

Icheon, KR

Email

iteratively@naver.com

Social

-->