BOJ 8129 The Invasion

문제 링크:

문제 내용

$n$개의 꼭짓점을 갖는 볼록 다각형과 그 내부의 $m$개의 점이 주어집니다. 각 점에는 가중치가 매겨져 있습니다. 볼록 다각형에서 3개의 서로 다른 꼭짓점을 선택하여 이들을 꼭짓점으로 하는 삼각형을 그렸을 때, 그 삼각형의 내부에 있는 모든 점의 가중치의 합이 최대가 되도록 하세요.

어떤 다각형의 테두리나 꼭짓점 위에 있는 점도 그 다각형의 내부에 있는 것입니다.

입력

첫 줄에는 다각형의 꼭짓점의 개수 $n$이 주어집니다. ($3 \le n \le 600$) 그다음 $n$줄에는 다각형의 꼭짓점의 좌표가 시계 방향으로 주어집니다. ($-10\;000 \le x, y \le 10\;000$)

그 다음 줄에는 점의 개수 $m$이 주어집니다. ($1 \le m \le 10\;000$) 그다음 $m$줄에는 각 점의 정보가 $x$좌표, $y$좌표, 가중치 $w$ 순으로 주어집니다. ($-10\;000 \le x, y \le 10\;000$, $-100\;000 \le w \le 100\;000$)

모든 점은 다각형의 내부에 있습니다. 여러 개의 점이 같은 위치에 있을 수도 있습니다.

출력

삼각형 내의 가중치의 합의 최댓값을 출력합니다.

문제 풀이