24894번 - 내적

$N$개의 2차원 벡터 $(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)$이 주어진다.

이 중 서로 다른 두 벡터를 골라 내적을 할 때 내적값의 최댓값을 구하시오.

두 벡터 $(x_i,y_i),\ (x_j,y_j)$의 내적값은 $x_ix_j + y_iy_j$로 정의한다.

첫째 줄에 벡터의 개수 $N$이 주어진다. ($2 \leq N \leq 300\,000$)

둘째 줄부터 $N+1$번째 줄까지 $i+1$번째 줄에 $i$번째 벡터의 두 성분 $x_i, y_i$가 공백으로 구분되어 주어진다. ($1 \leq x_i,y_i \leq 300\,000$, $x_i, y_i$는 정수)

모든 벡터는 서로 다르다.

서로 다른 두 벡터를 골라 내적을 할 때 내적값의 최댓값을 출력한다. 즉, $\displaystyle \max_{1\leq i,j \leq N,\ i \neq j} \left\{ x_ix_j + y_iy_j \right\}$ 를 출력한다.