Time limit: 1.4 / Memory limit: 256M

Point: 100

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ố xi,yi miêu tả tọa độ của điểm thứ i.

Output

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

Constraints .

  • 1n2000.
  • Tọa độ của các điểm đều là số nguyên trong khoảng [104,104].

Subtask

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

Sample Input 1

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

Sample Output 1

Copy
3

Tứ giác

Nộp bài
Time limit: 5.0 / Memory limit: 1G

Point: 100

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 (4N104) 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|105) 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
Copy
5
0 2
1 3
2 2
2 0
0 0
Output
Copy
4.0
Giải thích

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

Input
Copy
6
4 2
3 3
4 5
6 5
7 3
6 2
Output
Copy
6.5
Giải thích

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

Ràng buộc

  • 40% số test ứng với 40% số điểm có N50;
  • 30% số test khác ứng với 30% số điểm có N200;
  • 20% số test khác ứng với 20% số điểm có N2000;
  • 10% số test còn lại ứng với 10% số điểm không có ràng buộc gì thêm.

CutPoly

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho một đa giác lồi gồm n đỉnh, đỉnh thứ iPi. 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, ack cạnh nằm giữa bc. Đ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 abbc 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 xiyi là tọa độ của điểm Pi.
  • Tọa độ các điểm được nhập theo thứ tự ngược chiều kim đồng hồ.

Constraints

  • n105
  • 1kn2

Subtask

  • Subtask 1: n50 (40%)
  • Subtask 2: n200 (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:
Copy
8 3
1 2
3 1
5 1
7 3
8 6
5 8
3 7
1 5
Sample Output 1:
Copy
26.5
Sample Input 2:
Copy
7 2
3 6
1 1
3 1
7 1
8 1
5 6
4 6
Sample Output 2:
Copy
20.0    
Explanation :

Ví dụ 12 được minh họa qua hình vẽ sau:

Imgur


LineGame

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

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ố xi,yi 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 .

  • 1t5.
  • 1n105.
  • 35p100
  • Tọa độ của các điểm đều là số nguyên trong khoảng [109,109].

Subtask

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

Sample Input 1

Copy
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

Copy
possible
impossible

Explanation 1

Imgur

Ở 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.

Imgur

Ở 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.


MakePoly

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

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ố xi,yi miêu tả tọa độ của điểm thứ i.

Output

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

Constraints .

  • 1n300.
  • Tọa độ của các điểm đều là số nguyên trong khoảng [1,104].

Subtask

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

Sample Input 1

Copy
5
4 2
2 2
2 3
3 2
3 1

Sample Output 1

Copy
4

Sample Input 2

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

Sample Output 2

Copy
7

CNT Triangle

Nộp bài
Time limit: 3.0 / Memory limit: 512M

Point: 100

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

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

  • AB=CD
  • BC=DE
  • AC=CE
  • BAC=DCE
  • ABC=CDE
  • ACB=CED

Bạn cần đếm số bộ sáu số nguyên dương (i1,i2,i3,j1,j2,j3) sao cho chúng khác nhau đôi một và:

  • 1i1,i2,i3,j1,j2,j3n
  • i1<i2<i3
  • Pi1Pi2Pi3 không suy biến, nói cách khác nó có diện tích dương.
  • Pi1Pi2Pi3=Pj1Pj2Pj3

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 xiyi là tọa độ của điểm Pi.

Constraints

  • n100
  • 1xi,yi109

Subtask

  • Subtask 1: n,m10 (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:
Copy
6
2 2
4 6
6 2
14 8
10 6
14 4
Sample Output 1:
Copy
4
Explanation 1:

Imgur

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)

Time limit: 1.0 / Memory limit: 256M

Point: 100

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

Tập điểm A gồm a1,a2,...,an và tập điểm B gồm b1,b2,...,bm.

Gọi f(i,j,k) là số điểm bx nằm trong tam giác được tạo bởi ba đểm (ai,aj,ak).

Tính i=1n2j=i+1n1k=j+1nf(i,j,k).

Input

  • Dòng đầu tiên gồm hai số nguyên dương n,m (1n,m300);
  • n dòng sau, dòng thứ i gồm hai số nguyên xi,yi miêu tả tọa độ (xi,yi) của điểm ai (|xi|,|yi|109).
  • m dòng sau, dòng thứ i gồm hai số nguyên xi,yi miêu tả tọa độ (xi,yi) của điểm ai (|xi|,|yi|109).

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

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

Sample Output 1

Copy
2

Subtask

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