이 문제에서는 "직사각형의 최대 넓이"를 구하는 것이 목적이다. 따라서 직사각형의 특징에 중점을 두고 생각하자.

1. 두 대각선은 서로를 이등분한다. (평행사변형의 특징이나, 직사각형은 평행사변형의 성질을 모두 포함한다.)
2. 두 대각선의 길이가 같다. (사각형 중 다음을 만족하는 것은 등변 사다리꼴과 직사각형, 정사각형 뿐이다.)

이 두가지를 모두 만족하는 사각형이 있다면, 우리는 자신있게 "이 시각형은 직사각형이다."라고 말해도 될 것이다.
여기에 넓이가 최대인 순간을 효율적으로 찾아보자.

다음과 같이 한 대각선의 절반의 길이가 A이고 한 각이 인 직사각형이 있다면, 넓이는 다음과 같다.

과정은 약간 복잡하므로 생략하지만, 이 식으로 의 값이 90도에 가까워질수록 넓이의 값이 커지게 된다.

따라서 우리는 최대한 90도에 가까운 두 대각선을 선택하면 된다는 것을 알 수 있다.

이제 이 문제에 이 지식들을 적용해보자. 모든 "대각선"들을 모아서 정렬을 해준다. 이때의 정렬 기준은 다음과 같다.

1. 중점을 기준
2. 중점이 같다면, 길이를 기준
3. 길이마저 같다면, 기울기를 기준

이제 같은 중점과 같은 길이를 가지는 점들은 필히 연결이 된다는 것을 알 수 있다.

다음과 같이 중점과 길이가 같은 대각선들이 여러개의 그룹으로 모이게 된다.

이제 각 구간내에서 이중반복문으로 정답을 구해내는 방법도 AC가 된다.

하지만 개선하는 방법이 존재한다. 바로 위의 넓이의 최댓값을 이용하는 것이다.

sin 함수의 그래프를 보자. (그림 출처 : http://blog.naver.com/azu016?Redirect=Log&logNo=110045274891 )

는 90도이다. 이것으로 볼 수 있듯, 넓이는 90도 이전에는 증가하고, 90도 이후에는 감소하는 것을 알 수 있다.

중점의 좌표와 대각선이 같은 한 그룹이 있다. 첫번째 대각선은 네번째 대각선과 넓이가 최대가 된다고 하자.

그러면 넓이의 관계는 다음이 성립할 것이다. 사인함수와 같이 보면 더 이해가 잘될 것이다.

따라서 우리는 모든 부분을 탐색할 필요도 없이, 인접한 넓이를 비교해가며 최적이 되는 넓이를 구해내기만 하면 된다.

하지만 모든 대각선에 대하여 이렇게 구하는 것은 매우 비효율적이므로, 하나의 아이디어를 추가하자.

"모든 대각선은 각도순으로 정렬되어있으므로, 그 이전에 최적해가 아닌 부분을 고려할 필요는 없다."

이 아이디어를 이용해 Sliding Window 아이디어를 추가할 수 있다.

두번째 부분은, 마지막으로 정해가 된 부분부터 탐색을 하면 된다는 뜻이다. 이것으로 탐색의 횟수를 크게 줄일 수 있다.

여기에 마지막 아이디어를 추가해서, 탐색의 횟수를 더 줄여보자. 제일 마지막 대각선일 때 최댓값이 나온다면, 어떻게 효율적으로 처리할까?

마지막 탐색(네모 부분)은 더 이상 진행할 수 없으므로, 대상(동그라미)이 앞으로 오면서 비교를 해야한다. 여기서도 넓이는 사인함수의 그래프와 같이 특정 부분까지 증가하다, 감소하게 된다. 따라서 최대 증가 부분을 구하고 나면, 이후는 감소할 것이므로 더 탐색할 필요가 없다.

이 부분을 그냥 건너뛰게 되면 탐색의 횟수를 더 줄일 수 있게 된다.

마지막으로, 실수 연산을 피해서 정답을 구해보자.

별일 아닌 문제일 수 있으나, 좌표의 범위가 매우 크므로 실수연산으로 가게 되면 오차가 발생할 수 있다. 두 점의 거리를 구해서 곱하자니 실수오차가 생길 수 있고, 두 대각선에 2배를 한 후 sin함수를 취하자니 각도를 이용해야하기에 복잡하고 역시 실수오차가 생긴다.

이것을 어떻게 실수연산없이 구해낼 수 있을까?? 다음과 같은 그림이 해당 아이디어를 제공한다. 예제의 그림을 보면

여기서 직사각형은 항상 넓이가 정수임을 알 수 있다. 이것을 다음과 같이 구하면, 정수형으로 넓이를 쉽게 구할 수 있다.

초록색 부분을 넓이를 구해서 뺀다면, 직사각형의 부분만 남게 된다.

점 에 대하여 대각선의 수는 이고, 이 대각선을 정렬하므로 , 마지막 탐색 부분이 이므로 최종시간복잡도는 이다.

[BOI 2009] Rectangle 풀이