파일 업로드

놀이기구 설계

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

철수는 새로운 놀이공원을 설계하고 있습니다.

놀이공원의 2D 설계도에는 NN개의 놀이기구들(3N1003 \le N \le 100)이 어떠한 위치 (X1,Y1)(XN,YN)(X_1, Y_1) \ldots (X_N, Y_N)에 있습니다. 

그는 놀이기구들 중 세 개를 선택하여 삼각형의 새로운 어트랙션 구역을 만들 계획입니다. 단, 새로운 어트랙션 구역의 한 변은 xx-축에 평행하고, 다른 변은 yy-축에 평행해야 합니다.

철수가 만들 수 있는 어트랙션 구역의 최대 넓이는 얼마인가요? 적어도 하나의 유효한 삼각형 어트랙션 구역이 존재한다는 것이 보장되어 있습니다.

💻 입력

입력의 첫 번째 줄에는 정수 NN이 있습니다. 

다음 NN 줄 각각에는 놀이기구의 위치를 설명하는 두 개의 정수 XiX_iYiY_i가 있고, 이들은 모두 범위 104104-10^4 \ldots 10^4을 포함합니다.

🖨️ 출력

넓이 자체가 반드시 정수가 아니므로, 놀이기구들로 형성된 유효한 삼각형 어트랙션 구역의 최대 넓이를 두 배를 출력하세요.


💻 예제 입력 1
4
0 0
0 1
1 0
1 2
🖨️ 예제 출력 1
2

💡 힌트

(0,0)(0,0), (1,0)(1,0), 그리고 (1,2)(1,2) 위치에 있는 놀이기구들은 넓이 11의 삼각형을 형성합니다. 

따라서, 대답은 21=22 \cdot 1=2입니다. 다른 삼각형은 넓이 0.50.5가 한 개 있습니다.


출처: USACO 2020 February Contest, Bronze Problem 1. Triangles