아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

다이아몬드

시간 제한2초메모리 제한512 MB

요약
볼록 다면체가 주어질 때, 한 평면으로 잘라 생기는 두 조각의 면 수 합이 최대가 되도록 자르는 문제이다.
난이도

어려움10점 중 9점

유형
기하, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

잭은 보석 세공사입니다. 어느 날 유난히 크고 아름다운 다이아몬드 원석이 그의 가게로 들어왔습니다. 이 다이아몬드를 사고 싶어 하는 손님이 두 명 있어서, 잭은 다이아몬드를 두 조각으로 잘라 (두 조각의 무게가 반드시 같을 필요는 없습니다) 각 손님에게 한 조각씩 팔기로 했습니다.

다이아몬드는 매우 단단해서 다이아몬드 톱날이 달린 톱으로만 자를 수 있습니다. 절단은 비싸고 느려서, 2밀리미터를 자르는 데 약 한 시간이 걸립니다. 잭은 하나의 평면을 따라 단 한 번만 자를 수 있으며, 잘라서 얻은 두 조각은 모두 두 손님에게 판매됩니다.

잭은 두 손님을 최대한 만족시키고 싶습니다. 두 조각의 무게 합은 언제나 원래 다이아몬드 전체의 무게와 같으므로, 잭은 대신 두 조각이 가지는 면(face)의 총 개수를 최대로 만들기로 했습니다. 어떻게 잘라야 할지 몰라 당신에게 도움을 요청했습니다.

입력

첫 번째 줄에는 다이아몬드의 꼭짓점 개수를 나타내는 정수 nn (4≤n≤804 \le n \le 80)이 주어집니다. 이어지는 nn개의 줄에는 각각 세 정수 xix_i, yiy_i, ziz_i (−360≤xi,yi,zi≤360-360 \le x_i, y_i, z_i \le 360)가 공백 하나로 구분되어 주어지며, 이는 ii번째 꼭짓점의 좌표입니다. 다이아몬드는 주어진 모든 점을 포함하는 가장 작은 볼록 다면체입니다. 어떤 점도 다이아몬드의 내부에 있지 않으며, 어떤 네 꼭짓점도 한 평면 위에 있지 않습니다.

출력

다이아몬드를 하나의 평면으로 단 한 번 잘라서 얻은 두 조각이 가지는 면의 총 개수의 최댓값을 정수 하나로 출력합니다.

예제1

  1. 예제 1

    입력
    5
    0 0 0
    5 0 0
    0 5 0
    0 0 5
    2 2 2
    
    예상 출력
    14