Trên mặt phẳng tọa độ, cho ~n~ điểm có tọa độ nguyên. Hãy tính chu vi của bao lồi của tập điểm này.

Input

• Dòng đầu gồm số nguyên dương ~n~ là số điểm.
• ~n~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~x_i,y_i~ là tọa độ của điểm thứ ~i~.

Output

• In ra chu vi của bao lồi của tập điểm, kết quả lấy chính xác tới ~1~ chữ số thập phân.

Constraints

• ~3 \le n \le 10^4~.
• ~-10^4 \le x_i,y_i \le 10^4~.

Sample Input 1

6    
1 1    
2 5    
3 3    
5 3    
3 2    
2 2

Sample Output 1

12.2

Explanation 1

Bao lồi cần tìm gồm ~3~ điểm ~(1,1),(2,5),(5,3)~, có chu vi là ~12.200792856~.

Cho ~n~ điểm trên trục tọa độ ~Oxy~, hãy tìm bao lồi gồm nhiều đỉnh nhất của tập điểm đã cho.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ là số điểm.

• ~n~ dòng sau, mỗi dòng chứa ~2~ số ~x_i,y_i~ miêu tả tọa độ điểm thứ ~i~.

  Output

• In ra số đỉnh của bao lồi cần tìm.

Constraints

• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^6,10^6]~.

Sample Input 1

5
2 1
2 3
2 5
6 3
4 3

Sample Output 1

4

Explanation 1

Các đỉnh ~A,B,C,D~ nằm trong bao lồi cần tìm.

~3~ đỉnh ~A,C,D~ cũng tạo ra một bao lồi, tuy nhiên số đỉnh của nó không phải là tối đa.

~ABC~ đã được bầu làm Thị trưởng ~NoLand~ và cần xây dựng một khu vực để tổ chức cuộc họp liên quan đến các vấn đề của ~NoLand~.

Anh ấy yêu cầu một nhóm thợ xây đào ~n~ cái hố để cắm ~r~ cọc vào khu đất. Các cọc phải được đặt sao cho toàn bộ khu vực (tất cả các hố đã đào) đều được che phủ.

Chỉ có ~r~ cọc, anh ta có thể xây hội trường không?

Input

• Dòng đầu là số nguyên dương ~t~ - số test case.
• Với mỗi test case, dòng đầu chứa ~2~ số nguyên dương ~n,r~ là số hố và số cọc.

• ~n~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~x_i,y_i~ là tọa độ của các hố.

  Output

• Với mỗi test case, in ra ~0~ nếu không thể xây dựng hội trường, ngược lại in ra ~1~.

Constraints

• ~1 \le T \le 10~.
• ~3 \le n \le 10^4~.
• ~-10^5 \le x_i,y_i \le 10^5~.

Sample Input 1

1
5 4
1 0
2 0
1 1
1 2
1 3

Sample Output 1

1

Ở một nông trại nọ, có ~n~ cái cọc. Để bảo vệ con cừu của mình, bác nông dần cần dựng lên các rào chắn, sau đó đặt nó vào vị trí được bao bởi nhiều rào chắn nhất. Mỗi rào là một đa giác không tự cắt được tạo ra bằng cách nối các cái cọc lại với nhau bằng dây thừng, mỗi cái cọc thuộc không quá ~1~ rào chắn. Các rào phải được tạo ra sao cho với mỗi cặp rào chắn bất kì ~X~ và ~Y~ thì diện tích chung của ~X~ và ~Y~ là ~min (S(X), S(Y))~ hoặc ~0~.

Trên mặt phẳng tọa độ, các cái cọc được coi như các điểm với tọa độ nguyên. Hãy xác định xem con cừu sẽ được bảo vệ bởi tối đa bao nhiêu rào chắn.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng tiếp theo, lần lượt mỗi dòng chứa ~2~ số là tọa độ của các cọc.

Output

• In ra số nguyên duy nhất là kết quả của bài toán.

Constraints

• ~1 \le n \le 2000~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^4,10^4]~.

Sample Input 1

12
-9 -5
8 -4
-6 -4
0 -8
-4 -2
-3 -9
7 6
-2 9
-3 8
9 6
4 1
0 -7

Sample Output 1

2

Cho ~2~ tập điểm ~A~ và ~B~ trên trục tọa độ ~Oxy~. Một điểm của tập ~B~ được gọi là đẹp nếu vị trí của nó nằm trong một tam giác không suy biến (diện tích dương) có ba đỉnh thuộc tập điểm ~A~. Nếu điểm đó nằm trên cạnh của tam giác, ta cũng coi đó là một đỉnh tốt.

Yêu cầu: Cho biết tập điểm ~A~ và ~B~, hãy cho biết số điểm tốt của tập ~B~.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng tiếp theo, lần lượt mỗi dòng chứa ~2~ số là tọa độ của các điểm trong tập ~A~.
• Dòng tiếp theo gồm số nguyên dương ~k~.

• ~k~ dòng tiếp theo, lần lượt mỗi dòng chứa ~2~ số là tọa độ của các điểm trong tập ~B~.

  Output

• In ra số nguyên duy nhất là số điểm tốt của tập ~B~.

Constraints

• ~1 \le n,k \le 10^5~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^9,10^9]~.

Sample Input 1

6
1 2
1 5
3 1
3 3
5 2
5 3
4
2 2
3 4
4 2
4 5

Sample Output 1

3

Cho ~2~ tập điểm ~A~ và ~B~, hãy tìm một điểm trong tập ~A~ và một điểm trong tập ~B~ sao cho khoảng cách giữa chúng là lớn nhất, biết khoảng cách từ điểm ~a~ tới điểm ~b~ là ~\sqrt {(a.x-b.x)^2+(a.y-b.y)^2}~.

Input

• Dòng đầu gồm số nguyên dương ~n~ là số lượng điểm của cả ~2~ tập.

• ~n~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên ~x_i,y_i,c_i~ ~(-10^6 \le x_i,y_i \le 10^6, 0 \le c_i \le 1)~. Với ~x_i,y_i~ là tọa độ của điểm thứ ~i~ và ~c_i = 0~ nếu điểm này thuộc tập ~A~, ngược lại ~c_i = 1~ nếu điểm này thuộc tập ~B~. Đảm bảo rằng mỗi tập có ít nhất một điểm.

  Output

• In ra số nguyên duy nhất là khoảng cách xa nhất giữa ~2~ điểm trong các điểm đã cho. Kết quả lấy theo phần nguyên.

Constraints

• ~1 \le n \le 50000~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^6,10^6]~.

Subtask

• ~50\%~ số điểm có ~n \le 2000~.
• ~50\%~ còn lại không ràng buộc gì thêm.

Sample Input 1

5
1 5 1
-5 2 0
3 7 1
6 -2 0
5 1 0

Sample Output 1

9

Cho ~n~ điểm trên mặt phẳng tọa độ, hãy tìm ~3~ điểm sao cho chúng tạo thành một tam giác không suy biến và diện tích của nó là lớn nhất có thể.

Input

• Dòng đầu gồm số nguyên dương ~n~ là số lượng điểm.
• ~n~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên ~x_i,y_i~ ~(-10^7 \le x_i,y_i \le 10^7)~. Với ~x_i,y_i~ là tọa độ của điểm thứ ~i~.

Output

• In ra số nguyên duy nhất là diện tích tam giác lớn nhất được tạo thành từ ~3~ điểm trong các điểm đã cho. Kết quả lấy chính xác tới chữ số thập phân thứ nhất.

Constraints

• ~3 \le n \le 3000~.
• Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^7,10^7]~.

Subtask

• ~50\%~ số điểm có ~n \le 200~.
• ~50\%~ còn lại không ràng buộc gì thêm.

Sample Input 1

5
3 6
2 7
1 8
4 9
1 4

Sample Output 1

6.0