Hình Học Nâng Cao
CLINE
Nộp bàiPoint: 100
Cho
Input
- Dòng đầu gồm số nguyên dương
. dòng sau, mỗi dòng gồm hai số miêu tả tọa độ của điểm thứ .
Output
- In ra số bộ ba điểm thẳng hàng.
Constraints .
.- Tọa độ của các điểm đều là số nguyên trong khoảng
.
Subtask
- Sub
( ): . - Sub
( ): 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
Tứ giác
Nộp bàiPoint: 100
Trên hệ trục toạ độ
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
Dữ liệu vào từ tệp văn bản QUADIL.INP
:
- Dòng thứ nhất ghi số
là số đỉnh của đa giác lồi; dòng tiếp theo, mỗi dòng chứa hai số nguyên 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
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:
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:
Ràng buộc
- Có
số test ứng với số điểm có ; số test khác ứng với số điểm có ; số test khác ứng với số điểm có ; số test còn lại ứng với số điểm không có ràng buộc gì thêm.
CutPoly
Nộp bàiPoint: 100
Cho một đa giác lồi gồm
Giờ ta sẽ cắt đa giác
Tìm diện tích lớn nhất có thể của đa giác
Input
- Dòng đầu gồm số nguyên dương
. dòng sau, dòng thứ gồm hai số nguyên dương và là tọa độ của điểm .- Tọa độ các điểm được nhập theo thứ tự ngược chiều kim đồng hồ.
Constraints
Subtask
- Subtask
: - Subtask
: - Subtask
: Không có giới hạn gì thêm
Output
- In ra diện tích lớn nhất tìm được, lấy
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ụ
LineGame
Nộp bàiPoint: 100
Cho
Hãy xác định xem, có tồn tại một đường thẳng sao cho có ít nhất
Input
- Dòng đầu gồm số nguyên dương
miêu tả số bộ test. - Mỗi bộ test bao gồm:
- Dòng đầu gồm số nguyên dương
. - Dòng thứ hai gồm số nguyên dương
. dòng sau, mỗi dòng gồm hai số miêu tả tọa độ của điểm thứ .
- Dòng đầu gồm số nguyên dương
Đả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 .
. .- Tọa độ của các điểm đều là số nguyên trong khoảng
.
Subtask
- Sub
( ): . - Sub
( ): 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ụ
Ở ví dụ
MakePoly
Nộp bàiPoint: 100
Cho
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
Input
- Dòng đầu gồm số nguyên dương
. dòng sau, mỗi dòng gồm hai số miêu tả tọa độ của điểm thứ .
Output
- In ra số đỉnh nhiều nhất tìm được.
Constraints .
.- Tọa độ của các điểm đều là số nguyên trong khoảng
.
Subtask
- Sub
( ): . - Sub
( ): 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
CNT Triangle
Nộp bàiPoint: 100
Cho
Hai tam giác
Bạn cần đếm số bộ sáu số nguyên dương
không suy biến, nói cách khác nó có diện tích dương.
Input
- Dòng đầu gồm số nguyên dương
. dòng sau, dòng thứ gồm hai số nguyên dương và là tọa độ của điểm .
Constraints
Subtask
- Subtask
: - Subtask
: Không có giới hạn gì thêm
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ó
TriAB
Nộp bàiPoint: 100
Trên hệ trục tọa độ
Tập điểm
Gọi
Tính
Input
- Dòng đầu tiên gồm hai số nguyên dương
; dòng sau, dòng thứ gồm hai số nguyên miêu tả tọa độ của điểm . dòng sau, dòng thứ gồm hai số nguyên miêu tả tọa độ của điểm .
Dữ liệu đảm bảo tọa độ
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ó
số điểm có . - Có
số điểm không có ràng buộc gì thêm.