[백준/Python] (S2) 1198 - 삼각형으로 자르기

삼각형으로 자르기 

 

 

1198번: 삼각형으로 자르기

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

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로 시작해 조건에 맞을 때 마다 값을 증가시켜 모든 좌표를 돌 수 있게 구현하였다.