실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
철수는 새로운 놀이공원을 설계하고 있습니다.
놀이공원의 2D 설계도에는 개의 놀이기구들()이 어떠한 위치 에 있습니다.
그는 놀이기구들 중 세 개를 선택하여 삼각형의 새로운 어트랙션 구역을 만들 계획입니다. 단, 새로운 어트랙션 구역의 한 변은 -축에 평행하고, 다른 변은 -축에 평행해야 합니다.
철수가 만들 수 있는 어트랙션 구역의 최대 넓이는 얼마인가요? 적어도 하나의 유효한 삼각형 어트랙션 구역이 존재한다는 것이 보장되어 있습니다.
입력의 첫 번째 줄에는 정수 이 있습니다.
다음 줄 각각에는 놀이기구의 위치를 설명하는 두 개의 정수 와 가 있고, 이들은 모두 범위 을 포함합니다.
넓이 자체가 반드시 정수가 아니므로, 놀이기구들로 형성된 유효한 삼각형 어트랙션 구역의 최대 넓이를 두 배를 출력하세요.
4 0 0 0 1 1 0 1 2
2
, , 그리고 위치에 있는 놀이기구들은 넓이 의 삼각형을 형성합니다.
따라서, 대답은 입니다. 다른 삼각형은 넓이 가 한 개 있습니다.
출처: USACO 2020 February Contest, Bronze Problem 1. Triangles