Trên hệ tọa độ ~Oxy~, cho một đa giác lồi gồm ~n~ đỉnh. Có ~m~ truy vấn, mỗi truy vấn gồm một điểm, hãy kiểm tra xem điểm đó có nằm trong đa giác đã cho hay khô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~ trên đa giác. Các đỉnh được nhập vào theo thứ tự ngược chiều kim đồng hồ.
• Dòng tiếp theo gồm số nguyên dương ~m~.
• ~m~ dòng sau, mỗi dòng gồm hai số ~x_i,y_i~ miêu tả tọa độ của điểm thuộc truy vấn ~i~.

Output

• Gồm ~m~ dòng, dòng ~i~ in ra ~0~ nếu điểm thứ ~i~ không nằm trong đa giác, ngược lại in ra ~1~.

Constraints

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

Sample Input 1

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

Sample Output 1

0
0
1
1

Trên trục tọa độ ~Oxy~, cho tọa độ điểm ~I~. Có ~n~ đoạn thẳng và một số nguyên ~k~, đoạn thứ ~i~ có hai đầu mút là ~2~ điểm ~A_i~ và ~B_i~. Đường tròn có tâm ~I~ và bán kính ~R~ với ~R~ là số nguyên không âm, gọi tắt là ~(I,R)~, được gọi là tốt nếu chỉ có bé hơn hoặc bằng ~k~ đoạn thẳng có điểm nằm bên trong hoặc bên trên đường tròn.

Hãy tìm số nguyên không âm ~R~ lớn nhất sao cho đường tròn ~(I,R)~ là tốt.

Input

• Dòng đầu gồm hai số nguyên ~x_I,y_I~ miêu tả tọa độ của điểm ~I~.
• Dòng thứ hai gồm ~2~ số nguyên dương ~n~ và ~k~.
• ~n~ dòng sau, mỗi dòng gồm hai cặp số nguyên: ~x_{A_i},y_{A_i}~ và ~x_{B_i},y_{B_i}~ là hai đầu mút của đoạn thẳng thứ ~i~.

Output

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

Constraints .

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

Subtask

• Sub ~1~ (~50\%~): ~n \le 1000~ và tọa độ của các điểm đều nằm trong khoảng ~[-10^3,10^3]~.
• Sub ~2~ (~50\%~): Không giới hạn gì thêm.

Sample Input 1

0 0
4 2
-4 4 1 5
-3 2 -1 1
2 2 6 4
-3 -2 -1 -4

Sample Output 1

3

Explanation 1

Đường tròn tâm ~A~ với bán kính là ~3~ gồm ~2~ đoạn thẳng có điểm nằm bên trong hoặc bên trên đường tròn là ~DE~ và ~FG~, đây là bán kính lớn nhất thỏa mãn.

Cho ~n~ điểm trên mặt phẳng ~Oxy~. Hãy đếm số tam giác vuông được tạo thành từ ~3~ trong số ~n~ điểm trên.

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ố tam giác vuông được tạo thành.

Constraints .

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

Sample Input 1

5
-1 1
-1 0
0 0
1 0
1 1

Sample Output 1

7

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

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.

Input

• 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ồ.

Output

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

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

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

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~

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)~