/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
ABC250 は、 ABC1000 の開催を目指す高橋くんにとってちょうど 1/4 となる記念すべき回です。
そこで、高橋くんはピザを 1 枚買ってきて、そのピザのうちなるべく 1/4 に近い分量を食べて祝うことにしました。
高橋くんが買ってきたピザは凸 N 角形 (N \ge 4) の平らな形をしており、このピザを xy 平面上に置いた際、 i 番目の頂点の座標は (X_i,Y_i) でした。
高橋くんは、このピザを以下のように切って食べることにしました。
- まず、高橋くんはピザの頂点のうち隣接しない 2 頂点を選び、それらを通る直線に沿ってナイフを入れ、ピザを 2 つに切り分ける。
- その後、 2 つのピースのうち好きなものをどちらか 1 つ選んで食べる。
高橋くんが買ってきたピザの面積の 1/4 を a 、高橋くんが食べるピースの面積を b とした時、 8 \times |a-b| としてありえる最小値を求めてください。なお、この値は常に整数となることが示せます。
制約
- 入力は全て整数
- 4 \le N \le 10^5
- |X_i|, |Y_i| \le 4 \times 10^8
- 入力される頂点は反時計回りに凸 N 角形をなす。
入力
入力は以下の形式で標準入力から与えられる。
N X_1 Y_1 X_2 Y_2 \dots X_N Y_N
出力
答えを整数として出力せよ。
入力例 1
5 3 0 2 3 -1 3 -3 1 -1 -1
出力例 1
1
3 番目の頂点と 5 番目の頂点を通る直線に沿ってピザを切り分け、 4 番目の頂点を含む側のピースを食べたとします。
このとき、a=\frac{33}{2} \times \frac{1}{4} = \frac{33}{8} 、 b=4 、 8 \times |a-b|=1 であり、これがありえる最小値です。
入力例 2
4 400000000 400000000 -400000000 400000000 -400000000 -400000000 400000000 -400000000
出力例 2
1280000000000000000
入力例 3
6 -816 222 -801 -757 -165 -411 733 131 835 711 -374 979
出力例 3
157889
Score : 500 points
Problem Statement
ABC 250 is a commemorable quarter milestone for Takahashi, who aims to hold ABC 1000, so he is going to celebrate this contest by eating as close to 1/4 of a pizza he bought as possible.
The pizza that Takahashi bought has a planar shape of convex N-gon. When the pizza is placed on an xy-plane, the i-th vertex has coordinates (X_i, Y_i).
Takahashi has decided to cut and eat the pizza as follows.
- First, Takahashi chooses two non-adjacent vertices from the vertices of the pizza and makes a cut with a knife along the line passing through those two points, dividing the pizza into two pieces.
- Then, he chooses one of the pieces at his choice and eats it.
Let a be the quarter (=1/4) of the area of the pizza that Takahashi bought, and b be the area of the piece of pizza that Takahashi eats. Find the minimum possible value of 8 \times |a-b|. We can prove that this value is always an integer.
Constraints
- All values in input are integers.
- 4 \le N \le 10^5
- |X_i|, |Y_i| \le 4 \times 10^8
- The given points are the vertices of a convex N-gon in the counterclockwise order.
Input
Input is given from Standard Input in the following format:
N X_1 Y_1 X_2 Y_2 \dots X_N Y_N
Output
Print the answer as an integer.
Sample Input 1
5 3 0 2 3 -1 3 -3 1 -1 -1
Sample Output 1
1
Suppose that he makes a cut along the line passing through the 3-rd and the 5-th vertex and eats the piece containing the 4-th vertex.
Then, a=\frac{33}{2} \times \frac{1}{4} = \frac{33}{8}, b=4, and 8 \times |a-b|=1, which is minimum possible.
Sample Input 2
4 400000000 400000000 -400000000 400000000 -400000000 -400000000 400000000 -400000000
Sample Output 2
1280000000000000000
Sample Input 3
6 -816 222 -801 -757 -165 -411 733 131 835 711 -374 979
Sample Output 3
157889