Cho ~n~ điểm trên mặt phẳng ~Oxy~. Hãy đếm số bộ ba điểm thẳng hàng.

Input

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

Output

• In ra số bộ ba điểm thẳng hàng.

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]~.

Subtask

• Sub ~1~ (~50\%~): ~n \le 200~.
• Sub ~2~ (~50\%~): Không giới hạn gì thêm.

Sample Input 1

6
0 0
0 1
0 2
1 1
2 0
2 2

Sample Output 1

3

Trên hệ trục toạ độ ~Oxy~, cho một đa giác lồi được tạo bởi ~N~ điểm có toạ độ nguyên.

Yêu cầu: Hãy tìm hình tứ giác có diện tích lớn nhất được tạo bởi ~4~ trong ~N~ điểm của đa giác lồi đã cho.

Dữ liệu vào từ tệp văn bản QUADIL.INP:

• Dòng thứ nhất ghi số ~N~ ~(4 \le N \le 10^4)~ là số đỉnh của đa giác lồi;
• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x, y~ ~(|x|, |y| \le 10^5)~ biểu diễn toạ độ các đỉnh của đa giác. Thứ tự các đỉnh được liệt kê theo chiều kim đồng hồ.

Kết quả ghi ra tệp văn bản QUADIL.OUT:

Gồm một số duy nhất là diện tích lớn nhất của tứ giác tìm được. Kết quả lấy chính xác ~1~ chữ số sau phần thập phân.

Ví dụ

Input

5
0 2
1 3
2 2
2 0
0 0

Output

4.0

Giải thích

Chọn các đỉnh: ~(0, 2), (2, 2), (2, 0), (0, 0)~.

Input

6
4 2
3 3
4 5
6 5
7 3
6 2

Output

6.5

Giải thích

Chọn các đỉnh: ~(3, 3), (4, 5), (6, 5), (6, 2)~.

Ràng buộc

• Có ~40\%~ số test ứng với ~40\%~ số điểm có ~N \le 50~;
• ~30\%~ số test khác ứng với ~30\%~ số điểm có ~N \le 200~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~N \le 2000~;
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm không có ràng buộc gì thêm.

Cho một đa giác lồi gồm ~n~ đỉnh, đỉnh thứ ~i~ là ~P_i~. Bạn cần chọn ra ba điểm ~a,b,c~ phân biệt theo thứ tự ngược chiều kim đồng hồ thuộc ~P~, sao cho tồn tại đúng ~k~ cạnh từ ~b~ tới ~c~ theo thứ tự ngược chiều kim đồng hồ.

Giờ ta sẽ cắt đa giác ~P~ ra với hai đoạn ~ab~, ~ac~. Gọi ~Q~ là đa giác gồm ~ab~, ~ac~ và ~k~ cạnh nằm giữa ~b~ và ~c~. Đa giác này gồm ~k+2~ cạnh.

Tìm diện tích lớn nhất có thể của đa giác ~Q~. Chú ý rằng ~ab~ và ~bc~ có thể đồng thời là một cạnh của ~P~.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng sau, dòng thứ ~i~ gồm hai số nguyên dương ~x_i~ và ~y_i~ là tọa độ của điểm ~P_i~.
• Tọa độ các điểm được nhập theo thứ tự ngược chiều kim đồng hồ.

Constraints

• ~n \le 10^5~
• ~1 \le k \le n-2~

Subtask

• Subtask ~1~: ~n \le 50~ ~(40\%)~
• Subtask ~2~: ~n \le 200~ ~(30\%)~
• Subtask ~3~: Không có giới hạn gì thêm ~(30\%)~

Output

• In ra diện tích lớn nhất tìm được, lấy ~1~ chữ số sau dấu thập phân.

Sample Input 1:

8 3
1 2
3 1
5 1
7 3
8 6
5 8
3 7
1 5

Sample Output 1:

26.5

Sample Input 2:

7 2
3 6
1 1
3 1
7 1
8 1
5 6
4 6

Sample Output 2:

20.0    

Explanation :

Ví dụ ~1~ và ~2~ được minh họa qua hình vẽ sau:

Cho ~n~ điểm trên mặt phẳng ~Oxy~ và tham số ~p~.

Hãy xác định xem, có tồn tại một đường thẳng sao cho có ít nhất ~p~ phần trăm các điểm trong ~n~ điểm được cho nằm chính xác trên đường thẳng đó hay không.

Input

• Dòng đầu gồm số nguyên dương ~t~ miêu tả số bộ test.
• Mỗi bộ test bao gồm:
  • Dòng đầu gồm số nguyên dương ~n~.
  • Dòng thứ hai gồm số nguyên dương ~p~.
  • ~n~ dòng sau, mỗi dòng gồm hai số ~x_i,y_i~ miêu tả tọa độ của điểm thứ ~i~.

Đảm bảo rằng không có hai điểm nào trùng khớp.

Output

• Với mỗi bộ test, nếu tồn tại đường thẳng thỏa mãn thì in ra "possible", ngược lại in ra "impossible".

Constraints .

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

Subtask

• Sub ~1~ (~50\%~): ~n \le 1000~.
• Sub ~2~ (~50\%~): Không giới hạn gì thêm.

Sample Input 1

2
5
55
0 0
10 10
10 0
0 10
3 3
5
45
0 0
10 10
10 0
0 10
3 4

Sample Output 1

possible
impossible

Explanation 1

Ở ví dụ ~1~, tồn tại đường thẳng đi qua (ít nhất) ~3~ điểm trong số ~5~ điểm trên.

Ở ví dụ ~2~, không tồn tại đường thẳng nào đi qua nhiều hơn hoặc bằng ~45\%~ số điểm.

Cho ~n~ điểm trên mặt phẳng ~Oxy~.

Hãy tìm cách tạo ra một đa giác lồi gồm nhiều đỉnh nhất sao cho nó chỉ bao gồm điểm gốc tọa độ (điểm ~(0,0)~) và một số điểm trong ~n~ điểm đã cho.

Input

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

Output

• In ra số đỉnh nhiều nhất tìm được.

Constraints .

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

Subtask

• Sub ~1~ (~30\%~): ~n \le 20~.
• Sub ~2~ (~70\%~): Không giới hạn gì thêm.

Sample Input 1

5
4 2
2 2
2 3
3 2
3 1

Sample Output 1

4

Sample Input 2

10
9 6
1 7
2 2
3 9
8 7
3 2
9 4
3 1
9 7
6 9

Sample Output 2

7

Trên hệ trục tọa độ ~OXY~, cho hai tập điểm nguyên ~A~ và ~B~ lần lượt gồm ~n~ và ~m~ điểm.

Tập điểm ~A~ gồm ~a_1,a_2,...,a_n~ và tập điểm ~B~ gồm ~b_1,b_2,...,b_m~.

Gọi ~f(i,j,k)~ là số điểm ~b_x~ nằm trong tam giác được tạo bởi ba đểm ~(a_i,a_j,a_k)~.

Tính ~\sum_{i=1}^{n-2} \sum_{j=i+1}^{n-1} \sum_{k=j+1}^n f(i,j,k)~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n,m~ ~(1 \le n,m \le 300)~;
• ~n~ dòng sau, dòng thứ ~i~ gồm hai số nguyên ~x_i,y_i~ miêu tả tọa độ ~(x_i,y_i)~ của điểm ~a_i~ ~(|x_i|,|y_i| \le 10^9)~.
• ~m~ dòng sau, dòng thứ ~i~ gồm hai số nguyên ~x_i,y_i~ miêu tả tọa độ ~(x_i,y_i)~ của điểm ~a_i~ ~(|x_i|,|y_i| \le 10^9)~.

Dữ liệu đảm bảo tọa độ ~x~ của mọi điểm là phân biệt và không có bộ ba điểm nào thẳng hàng.

Output

• In ra kết quả của bài toán.

Sample Input 1

4 2
1 1
2 5
7 4
9 2
3 4
6 6

Sample Output 1

2

Subtask

• Có ~80\%~ số điểm có ~n,m \le 50~.
• Có ~20\%~ số điểm không có ràng buộc gì thêm.

Cho ~n~ điểm trên hệ trục tọa độ ~OXY~. Điểm thứ ~i~ gọi là ~P_i~.

Hai tam giác ~ABC~ và ~CDE~ được định nghĩa là bằng nhau nếu:

• ~AB = CD~
• ~BC = DE~
• ~AC = CE~
• ~\angle {BAC} = \angle {DCE}~
• ~\angle {ABC} = \angle {CDE}~
• ~\angle {ACB} = \angle {CED}~

Bạn cần đếm số bộ sáu số nguyên dương ~(i_1,i_2,i_3,j_1,j_2,j_3)~ sao cho chúng khác nhau đôi một và:

• ~1 \le i_1,i_2,i_3,j_1,j_2,j_3 \le n~
• ~i_1 < i_2 < i_3~
• ~\triangle {P_{i_1}P_{i_2}P_{i_3}}~ không suy biến, nói cách khác nó có diện tích dương.
• ~\triangle {P_{i_1}P_{i_2}P_{i_3}} = \triangle {P_{j_1}P_{j_2}P_{j_3}}~

Input

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

Constraints

• ~n \le 100~
• ~1 \le x_i , y_i \le 10^9~

Subtask

• Subtask ~1~: ~n,m \le 10~ ~(40\%)~
• Subtask ~2~: Không có giới hạn gì thêm ~(60\%)~

Output

• In ra số bộ sáu tìm được.

Sample Input 1:

6
2 2
4 6
6 2
14 8
10 6
14 4

Sample Output 1:

4

Explanation 1:

Ta có ~4~ bộ như sau:

• ~(1,2,3,4,5,6)~
• ~(1,2,3,4,6,5)~
• ~(4,5,6,1,2,3)~
• ~(4,5,6,1,3,2)~