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\mathrm{\%}$): $n\le 200$.
• Sub $2$ ($50\mathrm{\%}$): 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\mathrm{\%}$ số test ứng với $40\mathrm{\%}$ số điểm có $N\le 50$;
• $30\mathrm{\%}$ số test khác ứng với $30\mathrm{\%}$ số điểm có $N\le 200$;
• $20\mathrm{\%}$ số test khác ứng với $20\mathrm{\%}$ số điểm có $N\le 2000$;
• $10\mathrm{\%}$ số test còn lại ứng với $10\mathrm{\%}$ 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\mathrm{\%})$
• Subtask $2$: $n\le 200$ $(30\mathrm{\%})$
• Subtask $3$: Không có giới hạn gì thêm $(30\mathrm{\%})$

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\mathrm{\%}$): $n\le 1000$.
• Sub $2$ ($50\mathrm{\%}$): 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\mathrm{\%}$ 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\mathrm{\%}$): $n\le 20$.
• Sub $2$ ($70\mathrm{\%}$): 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

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$
• $\mathrm{\angle }BAC=\mathrm{\angle }DCE$
• $\mathrm{\angle }ABC=\mathrm{\angle }CDE$
• $\mathrm{\angle }ACB=\mathrm{\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$
• $\mathrm{△}{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.
• $\mathrm{△}{P}_{i_1}{P}_{i_2}{P}_{i_3}=\mathrm{△}{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\mathrm{\%})$
• Subtask $2$: Không có giới hạn gì thêm $(60\mathrm{\%})$

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

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\mathrm{\%}$ số điểm có $n,m\le 50$.
• Có $20\mathrm{\%}$ số điểm không có ràng buộc gì thêm.