시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
7 초 | 256 MB | 487 | 170 | 110 | 34.056% |
레프의 부대는 전장에 새 기지를 짓고, 여러 직선 벽으로 구성된 요새와 감시탑으로 이를 둘러싸기로 했다. 두 벽이 만나는 점에는 반드시 감시탑을 설치해야 하고, 전시에 조직적인 움직임을 위해 감시탑은 최대 4개까지만 설치하기로 했다
꼼꼼한 조사 끝에 레프는 탑의 무게를 견딜 수 있고, 시야 확보가 가능한 몇 군데의 점이 감시탑 설치에 적합하다고 판단했다.
프로그래밍을 배운 적이 없는 레프는 가장 넓은 기지를 짓기 위해 여러분에게 가능한 가장 넓은 기지의 넓이를 출력하는 프로그램을 짜 줄 것을 부탁했다. 하지만 정확한 위치는 군사 기밀이기 때문에, 위치는 입력으로만 주어지고, 또한 여러 가짜 데이터 속에 진짜 데이터를 숨길 수 있도록 많은 테스트 케이스를 다룰 수 있어야 한다는 조건을 추가했다. 레프를 만족하게 할 프로그램을 작성해 보자.
첫째 줄에 테스트 케이스의 개수 T(1≤T≤100)가 주어진다.
각각의 테스트 케이스에 대해, 테스트 케이스의 첫 줄에는 감시탑 건설에 적합한 위치의 수 n (3 ≤ n ≤ 1,000)이 주어지며, 이후 n개의 줄에는 감시탑 건설에 적합한 n개의 위치의 x, y좌표가 공백을 사이에 두고 주어진다. 모든 위치의 좌푯값은 모두 다르다.(-10,000 ≤ x, y ≤ 10,000)
각각의 테스트 케이스에 대해, 한 줄에 기지의 최대 넓이를 출력한다. 기지의 넓이가 반정수일 경우 "정수.5"의 형식으로 출력한다. 2.50000과 같이 뒤에 0을 출력할 경우 오답 처리한다.
3 6 0 0 3 7 10 0 11 6 0 10 10 10 5 0 0 -2 -2 3 -2 0 1 0 3 10 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4
100 12.5 31
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2014 C번