UselessTilePackers

원문보기

---

인기도:C(A,B,C), 성공률:보통(낮음,보통,높음), 레벨:3(1~4)

About UselessTilePackers

Useless Tile Packer라는 회사는 효율에 대한 자부심을 가지고 있다. 이 회사는 다른 회사보다 더 적은 공간을 사용하는 것을 가장 큰 목표로 삼고 있다. 영업부에서는 "useless(쓸모 없는)"라는 단어가 오해를 불러일으킬 수 있다고 생각하여 관리부에 회사 이름을 바꾸자고 여러 번 요청했지만 매번 거절당했다.

포장해야 할 타일은 모두 두께가 같고, 간단한 다각형 모양으로 생겼다. 각 타일이 담겨있는 용기 모양은 주문자가 마음대로 정할 수 있다. 용기 모양은 그 안에 들어갈 타일을 담을 수 있는 가장 작은 형태로 제작된다. [1] 하지만 이렇게 하면 용기 안에 낭비되는 공간이 생긴다. 타일이 주어졌을 때 낭비되는 공간의 비율을 계산해야 한다.

Input

입력 파일은 여러 데이터 블록으로 구성될 수 있다. 각 데이터 블록은 하나씩의 타일을 기술한다. 데이터 블록 첫째 줄에는 타일의 꼭지점의 개수를 나타내는 정수 N(3≤N≤100)이 입력된다. 그 밑으로는 N줄에 걸쳐서 각 꼭지점의 (x,y) 좌표를 나타내는 정수가 두 개씩 입력된다. 이때 x,y는 모두 0 이상 1,000 이하다. 꼭지점은 입력된 순서 그대로 연결된다. 세 개 이상의 동일 직선 상에 있는 점이 연속으로 입력되는 일은 없다. N으로 0이 입력되면 입력이 종료된다.

Output

입력된 각 타일에 대해 출력 예에 나와있는 것과 같은 식으로 타일 번호(1부터 시작)를 출력하고, 그 다음 줄에 "Wasted Space = X %" 형식으로 낭비된 공간의 비율을 퍼센트 단위로 출력한다. X는 낭비된 공간의 비율을 퍼센트로 나타낸 것이며, 소수점 아래로 둘째 자리까지 반올림해서 출력한다. 서로 다른 데이터 블록에 대한 결과 사이에는 빈 줄을 하나씩 출력한다.

Sample Input

5

0 0 2 0 2 2 1 1 0 2 5 0 0 0 2 1 3 2 2 2 0 0

Sample Output

Tile #1

Wasted Space = 25.00 %

Tile #2 Wasted Space = 0.00 %

풀이

작성자

사용언어

개발시간

코드

쓰레드

---

문제분류 경시대회준비반