안녕하세요,
재재입니다.
BOJ 10321 요새 건설 문제에 대한 풀이입니다.
BOJ 10321 요새 건설
(1) 문제 설명
분류 : geometry, convex hull
(convex hull 을 활용하는 다른 문제)
출처 : https://www.acmicpc.net/problem/10321
(1000이하) N개의 점의 좌표가 들어온다.
삼각형 혹은 사각형을 만들었을 때,
최대 넓이를 구해주면 됩니다.
(2) 풀이 도출
convex hull 을 구성하고,
convex hull 위의 점을 사용하면 된다.
- convex hull이 삼각형일 때, 넓이를 구하면 된다.
- convex hull이 삼각형이 아닐 때는, 사각형의 대각선(AB)을 정한다.
그리고 A부터 B사이의 적당한 점 p와 B부터 A사이의 적당한 점 q를 잡고,
삼각형의 넓이를 늘리는 방향으로 p와 q를 옮겨주면 된다.
만일 대각선이 AB일 때 최적의 점이 p, q라면
대각선이 AC일 때 최적의 점은 p, q 혹은,
그 다음 점들이 최적의 점의 후보군이 될 수 있다.
(이전의 점일 수는 없음)
위 성질을 이용하면,
전체 시간복잡도$$ O(n^2) $$ 에 해결 할 수 있습니다.
BOJ 10321 요새 건설