Cho ~3~ điểm tọa độ nguyên trên lưới tọa độ ~Oxy~, hãy xác định xem ~3~ điểm này có tạo thành hình tam giác được hay không?

Input

• ~3~ điểm có tọa độ nguyên.

Output

• In ra ~0~ nếu ~3~ điểm đã cho không thể tạo được một tam giác, ngược lại in ra ~1~.

Constraints

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

Sample Input 1

0 0 0 1 1 0

Sample Output 1

1

Sample Input 2

727 1 727 2 727 3

Sample Output 2

0

Cho một đa giác lồi ~n~ đỉnh, các đỉnh được nhập theo thứ tự ngược chiều kim đồng hồ.

Hãy tính diện tích của đa giác lồi đã 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~ trên đa giác.

Output

• In ra kết quả của bài toán lấy đến số thập phân thứ nhất.

Constraints

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

Sample Input 1

4
6 1
7 4
2 5
1 1 

Sample Output 1

18.0

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

Cho tam giác ~ABC~ trên hệ trục tọa độ ~Oxy~.

Hãy tính và in ra lần lượt các góc ~\angle BAC~, ~\angle CBA~, ~\angle ACB~.

Input

• Gồm ~3~ dòng, mỗi dòng gồm ~2~ số nguyên ~x,y~ miêu tả tọa độ của lần lượt các điểm ~A,B,C~.

Output

• Gồm ~3~ dòng, mỗi dòng in ra số góc của lần lượt các góc ~\angle BAC~, ~\angle CBA~, ~\angle ACB~, kết quả lấy đến số thập phân thứ ~6~.

Constraints

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

Sample Input 1

3 2
1 5
2 8

Sample Output 1

24.227745
127.874984
27.897271

Sample Input 2

1 5
1 2
4 2

Sample Output 2

45.000000
90.000000
45.000000

Trên hệ trục tọa độ ~Oxy~, có ~n~ điểm có tọa độ nguyên. Hãy tính khoảng cách xa nhất của ~2~ điểm trong số ~n~ điểm đã cho.

Nếu có ~1~ điểm thì in ra ~0.00~.

Input

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

Output

• In ra kết quả của bài toán với độ chính xác ~2~ chữ số sau dấu phẩy.

Constraints

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

Sample Input 1

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

Sample Output 1

8.94

Sample Input 2

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

Sample Output 2

17.46

Trên hệ trục tọa độ ~Oxy~, cho điểm ~P~ có tọa độ nguyên và ~n~ đường thẳng, đường thẳng thứ ~i~ đi qua ~2~ điểm ~A_i~ và ~B_i~.

Hãy tính độ dài dài nhất của khoảng cách từ điểm ~P~ tới một trong các đường thẳng đã cho.

Input

• Dòng đầu gồm hai số nguyên ~x_P~ ~y_P~ miêu tả tọa độ của điểm ~P~.
• Dòng thứ hai chứa số nguyên dương ~n~ miêu tả số đường thẳng.
• ~n~ dòng sau, dòng thứ ~i~ gồm ~4~ số nguyên dương ~x_A, y_A, x_B, y_B~ miêu tả tọa độ của hai điểm ~A,B~ mà đường thẳng ~i~ đi qua.

Output

• In ra kết quả của bài toán với độ chính xác ~2~ chữ số sau dấu phẩy.

Constraints

• ~n \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

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

Sample Output 1

2.77

Sample Input 2

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

Sample Output 2

2.24

Trên hệ trục tọa độ ~Oxy~, cho điểm ~P~ có tọa độ nguyên và ~n~ đoạn thẳng, đoạn thẳng thứ ~i~ có ~2~ đầu mút là ~A_i~ và ~B_i~.

Hãy tính độ dài dài nhất của khoảng cách ngắn nhất từ điểm ~P~ tới một trong các đoạn thẳng đã cho.

Input

• Dòng đầu gồm hai số nguyên ~x_P~ ~y_P~ miêu tả tọa độ của điểm ~P~.
• Dòng thứ hai chứa số nguyên dương ~n~ miêu tả số đường thẳng.
• ~n~ dòng sau, dòng thứ ~i~ gồm ~4~ số nguyên dương ~x_A, y_A, x_B, y_B~ miêu tả tọa độ của hai điểm ~A,B~ là đầu mút của đoạn thẳng ~i~.

Output

• In ra kết quả của bài toán với độ chính xác ~2~ chữ số sau dấu phẩy.

Constraints

• ~n \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

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

Sample Output 1

4.12

Sample Input 2

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

Sample Output 2

3.16

Trên hệ trục tọa độ ~Oxy~, cho ~2~ đường thẳng. Với mỗi đường thẳng, ta biết được hai điểm mà nó đi qua.

Hãy tìm giao điểm của hai đường thẳng đã cho.

Input

• Dòng đầu gồm hai cặp số nguyên: ~x_A,y_A~ và ~x_B,y_B~ là hai điểm mà đường thẳng thứ nhất đi qua.
• Dòng sau gồm hai cặp số nguyên: ~x_C,y_C~ và ~x_D,y_D~ là hai điểm mà đường thẳng thứ hai đi qua.

Output

• In ra trên một dòng tọa độ giao điểm của hai đường thẳng, kết quả của bài toán lấy tới ~3~ chữ số sau dấu phẩy, nếu hai đường thẳng song song hoặc trùng nhau in ra ~-1~.

Constraints .

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

Sample Input 1

3 2 6 8
-1 -2 7 -2

Sample Output 1

1.000 -2.000

Sample Input 2

-2 2 3 5
1 -2 11 4

Sample Output 2

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

Subtask

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

Sample Input 1

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

Sample Output 1

7