가끔 아무생각없이 알고리즘이나 풀었으면 한다.
요새 건설 성공다국어
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
7 초 256 MB 540 186 123 36.070%
문제
레프의 부대는 전장에 새 기지를 짓고, 여러 직선 벽으로 구성된 요새와 감시탑으로 이를 둘러싸기로 했다. 두 벽이 만나는 점에는 반드시 감시탑을 설치해야 하고, 전시에 조직적인 움직임을 위해 감시탑은 최대 4개까지만 설치하기로 했다
꼼꼼한 조사 끝에 레프는 탑의 무게를 견딜 수 있고, 시야 확보가 가능한 몇 군데의 점이 감시탑 설치에 적합하다고 판단했다.
프로그래밍을 배운 적이 없는 레프는 가장 넓은 기지를 짓기 위해 여러분에게 가능한 가장 넓은 기지의 넓이를 출력하는 프로그램을 짜 줄 것을 부탁했다. 하지만 정확한 위치는 군사 기밀이기 때문에, 위치는 입력으로만 주어지고, 또한 여러 가짜 데이터 속에 진짜 데이터를 숨길 수 있도록 많은 테스트 케이스를 다룰 수 있어야 한다는 조건을 추가했다. 레프를 만족하게 할 프로그램을 작성해 보자.
입력
첫째 줄에 테스트 케이스의 개수 T(1≤T≤100)가 주어진다.
각각의 테스트 케이스에 대해, 테스트 케이스의 첫 줄에는 감시탑 건설에 적합한 위치의 수 n (3 ≤ n ≤ 1,000)이 주어지며, 이후 n개의 줄에는 감시탑 건설에 적합한 n개의 위치의 x, y좌표가 공백을 사이에 두고 주어진다. 모든 위치의 좌푯값은 모두 다르다.(-10,000 ≤ x, y ≤ 10,000)
출력
각각의 테스트 케이스에 대해, 한 줄에 기지의 최대 넓이를 출력한다. 기지의 넓이가 반정수일 경우 "정수.5"의 형식으로 출력한다. 2.50000과 같이 뒤에 0을 출력할 경우 오답 처리한다.
뭔가 쉬워보이는데 여러 생각이 들다가 결국 블로그 글을 참고했던 문제이다.
convex_hull로 볼록껍질을 구하는것 자체는 상당히 간단한 일이지만, 여러가지 고려해야 할게 많았던 문제였다.
convex_hull 개수?
결국은 볼록껍질을 구하는것이라 4개 이상 나온다는 보장이 없다.
커다란 삼각형 안에 나머지 점들이 모두 포함되어 있다면 convex_hull의 개수가 3개가 될 것이고,
사각형 계산식을 적용한다면 재대로 구해지지 않는다.
따라서 3개일때는 삼각형 공식을 사용해줘야 한다.
계산 방법
처음 생각했던것은 모든 대각선을 구해서 각각을 사각형의 대각선이라 가정하고 사각형의 넓이를 구하는 것이다.
하지만 계산을 하고 고민을 해보니 다음과 같은 문제가 발생했다.
- 대각선의 요소가 중첩되는 경우([A,C] - [B,C] 처럼 끝값이 중복됨)
- 계산량이 많다. 1000개 점에 대각선 구하는것만해도 n^2인데 여기에 한번더 곱하면 O(n^3)이 나온다.
- 찌그러진 타원형인 경우를 생각해보면 정답과 관계없는 계산량이 너무 많다.
등등을 생각해서, 적어도 한 선분의 좌/우를 각각 나눠 따로 삼각형 계산을 해야겠다고 생각했다.
이후 한참을 코드실수와 씨름하면서 도전했고
블로그를 보다가 큰 힌트를 하나 얻게 된다.
n = len(hull)
ans = 0
for i in range(n):
p = (i + 1) % n
q = (i + 3) % n
for j in range(i + 2, n):
if i == 0 and j == n - 1:
continue
레퍼런스 : https://justicehui.github.io/icpc/2019/02/04/BOJ10321/
블로그 글을 참고해서 적은 코드이다.
i - j를 기준으로 왼쪽과 오른쪽에 p,q를 놓고, ijp / ijq의 삼각형 넓이의 합의 max값을 찾는 방법이다.
여기서 놀라웠던 점은 i가 n-2가 되더라도, j는 n이상 올라가지 않는다는 것이다.
왜그럴까 고민을 해 보니..
p - q를 하나의 대각선으로 잡는다고 생각해보니 이해가 되었다.
즉, i-j, p-q을 두 대각선으로 가지는 사각형의 넓이를 이미 모두 구했기 때문에, 더이상의 계산은 중복계산이 되는 것이다.
추가)
Convex_Hull을 구할때 그라함/모노톤 2개 중에 고민을 하게 되는데
어차피 이 둘의 차이는 문자가 어떻게 정렬되어있느냐의 차이라서
속편하게 모노톤을 쓰기로 했다.
모노톤은 최대연산량이 sort()라서 예측이 가능하지만
그라함을 쓸때 부동소수점 계산이 들어가기 때문에 사용이 꺼려진다.
알고리즘 풀면서
개발자가 공부를 잘하기 위해서 영어를 필수로 배워야 하듯이,
알고리즘 공부를 하려면 c++ 공부는 필수라는 생각이 들었다.
이제와서 c++로 마이그레이션 해야하나..?
