# [Silver II] 삼각형으로 자르기 [문제 링크](https://www.acmicpc.net/problem/1198) ## 문제 설명 <p>볼록 다각형이 있고, 여기서 3개의 연속된 점을 선택해서 삼각형을 만든다. 그 다음, 만든 삼각형을 다각형에서 제외한다. 원래 다각형이 N개의 점이 있었다면, 이제 N-1개의 점으로 구성된 볼록 다각형이 된다. 위의 과정은 남은 다각형이 삼각형이 될 때까지 반복한다.</p> <p>볼록 다각형의 점이 시계 방향순으로 주어진다. 마지막에 남은 삼각형은 여러 가지가 있을 수 있다. 이때, 가능한 넓이의 최댓값을 구하는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 볼록 다각형 점의 수 N (3 ≤ N ≤ 35)이 주어진다. 둘째 줄부터 N개의 줄에는 볼록 다각형을 이루고 있는 점이 시계 방향 순서로 주어진다. 좌표는 10,000보다 작거나 같은 자연수이다.</p> ## 출력 <p>첫째 줄에 문제의 정답을 출력한다. 절대/상대 오차는 10^-9까지 허용한다.</p> ## 풀이 임의의 세 점으로 이루어진 삼각형을 모두 만들 수 있기 때문에, 모든 삼각형의 넓이를 신발끈 공식으로 구해보면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; struct pos { int x, y; }; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<pos> v(n); for(int i=0;i<n;i++) cin >> v[i].x >> v[i].y; 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++) { maxArea = max(maxArea, abs(v[i].x*v[j].y+v[j].x*v[k].y+v[k].x*v[i].y-(v[i].x*v[k].y+v[j].x*v[i].y+v[k].x*v[j].y))/2.0); } } } cout << setprecision(9) << fixed << maxArea; } ```