[BOJ] 1198 - 삼각형으로 자르기

https://www.acmicpc.net/problem/1198

BOJ - 삼각형으로 자르기

문제 유형: 기하학, 브루트 포스

문제 난이도: Silver II

시간 제한: 2초

메모리 제한: 128MB

 

문제

볼록 다각형이 있고, 여기서 3개의 연속된 점을 선택해서 삼각형을 만든다. 그 다음, 만든 삼각형을 다각형에서 제외한다. 원래 다각형이 N개의 점이 있었다면, 이제 N-1개의 점으로 구성된 볼록 다각형이 된다. 위의 과정은 남은 다각형이 삼각형이 될 때까지 반복한다.

볼록 다각형의 점이 시계 방향순으로 주어진다. 마지막에 남은 삼각형은 여러 가지가 있을 수 있다. 이때, 가능한 넓이의 최댓값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 볼록 다각형 점의 수 N (3 ≤ N ≤ 35)이 주어진다. 둘째 줄부터 N개의 줄에는 볼록 다각형을 이루고 있는 점이 시계 방향 순서로 주어진다. 좌표는 10,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 문제의 정답을 출력한다. 절대/상대 오차는 10^-9까지 허용한다.

 

풀이

볼록 다각형은 삼격형들의 조합이다.

가장 작은 삼각형들만 빼서 남은 최대 크기의 삼각형은 볼록 다각형에서의 꼭짓점들 중에서 세 개를 뽑아서 가장 큰 삼각형이 된다.

 

세 점의 좌표가 주어지면, 우린 공식을 이용하여 삼각형의 크기를 구할 수 있다:

점을 a, b, c라 했을 때,

0.5 * |(a.x *  (b.y - c.y) + b.x *  (c.y - a.y) + c.x *  (a.y - b.y))|이다.

 

부동소수점 출력에 유의해야 한다. setprecision()을 이용했다.

 

코드

C++

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

double calculateArea(pii a, pii b, pii c) {
  return abs(0.5 * (a.first * (b.second - c.second) +
                    b.first * (c.second - a.second) +
                    c.first * (a.second - b.second)));
}

int main() {
  int n;
  cin >> n;

  vector<pii> points(n);
  for (int i = 0; i < n; ++i) {
    cin >> points[i].first >> points[i].second;
  }

  double maxarea = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      for (int k = j + 1; k < n; ++k) {
        auto a = points[i];
        auto b = points[j];
        auto c = points[k];

        double area = calculateArea(a, b, c);
        maxarea = max(maxarea, area);
      }
    }
  }

  cout << fixed << setprecision(9) << maxarea << "\n";
  return 0;
}