Dot Product

Time limit2sMemory limit1024 MB

Summary

Given N vectors with positive integer coordinates, find the maximum dot product of two distinct vectors in the set.

Level: Medium7 of 10
Topics: Geometry, Sorting
Solved: No attempts yet

Problem

$N$ two-dimensional vectors $(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)$ are given.

Choose two different vectors from these and find the maximum value of their dot product.

The dot product of two vectors $(x_i,y_i),\ (x_j,y_j)$ is defined as $x_ix_j + y_iy_j$ .

Input

The first line contains the number of vectors $N$ . ( $2 \leq N \leq 300\,000$ )

From the second line through line $N+1$ , the two components $x_i, y_i$ of the $i$ -th vector are given separated by a space. ( $1 \leq x_i,y_i \leq 300\,000$ , $x_i, y_i$ are integers)

All vectors are distinct.

Output

Print the maximum dot product of two different vectors chosen from the set. That is, print $\displaystyle \max_{1\leq i,j \leq N,\ i \neq j} \left\{ x_ix_j + y_iy_j \right\}$ .

Examples2

Example 1
Input
```
5
8 7
4 8
3 4
2 5
3 7
```
Expected output
```
88
```
Example 2
Input
```
8
1 1
1 2
1 3
1 4
4 7
4 11
7 6
9 5
```
Expected output
```
94
```