삼각형으로 자르기
2 초 | 128 MB | 1025 | 554 | 485 | 53.949% |
문제
볼록 다각형이 있고, 여기서 3개의 연속된 점을 선택해서 삼각형을 만든다. 그 다음, 만든 삼각형을 다각형에서 제외한다. 원래 다각형이 N개의 점이 있었다면, 이제 N-1개의 점으로 구성된 볼록 다각형이 된다. 위의 과정은 남은 다각형이 삼각형이 될 때까지 반복한다.
볼록 다각형의 점이 시계 방향순으로 주어진다. 마지막에 남은 삼각형은 여러 가지가 있을 수 있다. 이때, 가능한 넓이의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 볼록 다각형 점의 수 N (3 ≤ N ≤ 35)이 주어진다. 둘째 줄부터 N개의 줄에는 볼록 다각형을 이루고 있는 점이 시계 방향 순서로 주어진다. 좌표는 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 문제의 정답을 출력한다. 절대/상대 오차는 10-9까지 허용한다.
예제 입력 1 복사
3
1 1
2 3
3 2
예제 출력 1 복사
1.5
예제 입력 2 복사
4
1 1
1 2
3 3
2 1
예제 출력 2 복사
1.5
예제 입력 3 복사
8
1 2
1 3
2 4
3 4
4 3
4 2
3 1
2 1
예제 출력 3 복사
3.0
예제 입력 4
7
6 2
2 1
1 2
1 4
2 6
5 6
6 5
예제 출력 4 복사
10.0
일단, 좌표를 받아서 삼각형을 만들어야된다.
이때, 삼각형을 만들고 그 만든 삼각형은 제외 시켜야 한다.
이 점에서 일단 점을 조합을 이용해서 풀어야된다고 생각했다.
삼각형을 이루는 점의 수는 3개이다. 즉, 입력된 좌표값 중 3개를 뽑아서 만들어야한다.
수학 중, 순열과 조합의 수를 구하는 식이 있다.
촤표n개에서 만들 수 있는 삼각형의 수는 n개 중, 3개를 뽑아 만들 수 있는 조합의 수니깐
nC3으로 구한다.
이때 nC3은 n * n-1 * n-2 / 3 * 2 * 1이다.
반복되는 횟수를 구했으니, 이제 좌표값을 조건을 줘서 넓이를 구하면 된다.
넓이를 구하는 식은 여러가지 있지만, 좌표가 주어졌다는 점을 착안해 다음 식을 쓴다.
이 공식은 다음과 같이 풀면 된다.
파란 화살표가 이어진것 끼리 곱해서 파란 화살표끼리 더하고, 빨간 화살표가 이어진 것 끼리 곱해서 빨간화살표끼리 더한 후, 빨간 화살표, 파란 화살표를 뺀 것의 절댓값을 씌우고, 2로 나눠주면 된다.
그리하여 풀이는 다음과 같다.
#1198 삼각형으로 자르기
n = int(input())
def multiple(n,m):
s = 1
for i in range(n,m-1,-1):
s *= i
return s
arr = []
for _ in range(n):
arr.append(list(map(int,input().split())))
i = 0
j = 1
k = 2
m = 0
for _ in range(multiple(n,n-3 + 1) // multiple(3,1)):
if k > n - 1:
j += 1
k = j + 1
if j > n - 2:
i += 1
j = i + 1
k = j + 1
pos1 = arr[i]
pos2 = arr[j]
pos3 = arr[k]
area = abs(((pos1[0] * pos2[1] + pos2[0]*pos3[1] + pos3[0] * pos1[1]) - (pos1[0] * pos3[1] + pos3[0] * pos2[1] + pos2[0] * pos1[1])) / 2)
k += 1
if m < area:
m = area
print(m)
리스트의 인덱스 값을 ijk로 두어 012로 시작해 조건에 맞을 때 마다 값을 증가시켜 모든 좌표를 돌 수 있게 구현하였다.
'Study > CodingTest' 카테고리의 다른 글
[백준/Python] (G5)5430 - AC (0) | 2023.07.25 |
---|---|
[백준/Python] (S4)1755 - 숫자놀이 (0) | 2023.07.14 |
[백준/Python] (S4) 17218 - 비밀번호 만들기 (0) | 2023.07.08 |
[백준/Python] (S4)11399 - ATM (0) | 2023.07.08 |
[백준/Python] (S4)11047 - 동전 0 (0) | 2023.07.08 |