Đề thi chọn HSG

TỔNG QUAN BÀI THI

Tên bài
File chương trình
File dữ liệu vào
File kết quả

Bài 1
Tam giác
TAMGIAC.*
TAMGIAC.INP
TAMGIAC.OUT

Bài 2
Gặp nhau
GAPNHAU.*
GAPNHAU.INP
GAPNHAU.OUT

Bài 3
Domino
DOMINO.*
DOMINO.INP
DOMINO.OUT

Dấu * được thay thế bởi PAS, PP hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++
Hãy lập trình để giải các bài toán sau:
Bài 1: Tam giác (6 điểm)
Trong mặt phẳng toạ độ Oxy cho N điểm, mỗi điểm Ni được xác định bởi cặp toạ độ nguyên xi, yi. (1 ( i ( 100)
Hãy tính diện tích của tất cả các tam giác được tạo thành từ 3 điểm phân biệt không thẳng hàng và chứa điểm N1(x1, y1). Ghi diện tích các tam giác tìm được vào tệp TAMGIAC.OUT theo thứ tự tăng dần.
Biết công thức tính diện tích tam giác:
và
với a, b, c là độ dài của 3 cạnh của tam giác.
Dữ liệu vào: được cho trong tệp TAMGIAC.INP gồm có các dòng:
- Dòng đầu tiên có 1 số nguyên dương N (1 ( N ( 100) .
- Các dòng tiếp theo ghi các cặp số nguyên (các số cách nhau ít nhất một kí tự trắng) là tọa độ của đỉểm Ni tương ứng.
Dữ liệu ra: được ghi vào tệp TAMGIAC.OUT gồm:
- Mỗi dòng ghi diện tích của một tam giác theo thứ tự tăng dần (lấy 2 chữ số thập phân). Nếu không tồn tại tam giác thì ghi là NULL.
Ví dụ:
TAMGIAC.INP
TAMGIAC.OUT

5
2 7
6 4
5 -2
-1 -2
-2 4
12.00
13.50
13.50
22.50
22.50
27.00


Bài 2: Gặp nhau(7 điểm)
Hoà và Thân là bạn thân của nhau, hai người xa nhau đã lâu, nay mới liên lạc được với nhau qua Internet và họ hẹn gặp nhau tại thành phố Hồ Chí Minh. Họ quyết định đến gặp nhau bằng cách đi máy bay để tiết kiệm thời gian. Hoà và Thân sinh sống và làm việc tại hai thành phố khác nhau.
Hãy tìm cách giúp Hoà và Thân đến được thành phố Hồ Chí Minh bằng các chuyến bay có thể có nhưng để tiết kiệm chi phí, tại mỗi sân bay mỗi người chỉ được ghé lại 1 lần và mỗi người phải qua ít thành phố nhất.
Các thành phố xem như là các đỉnh của một đồ thị vô hướng gồm N đỉnh được mã số từ 1 đến N (1 ( i ( 100). Chỉ một số cặp thành phố mới có đường bay còn lại thì không. Giả sử đỉnh xuất phát không trùng đỉnh đích.
Dữ liệu vào: được cho trong tệp GAPNHAU.INP gồm có các dòng:
- Dòng đầu tiên, được gọi là dòng 0, chứa 4 số tự nhiên N, H, T, D(1(H,T,D(N), trong đó N là số thành phố có sân bay, H là nơi Hoà đang sinh sống và công tác còn T là thành phố mà Thân sống và làm việc, D là mã số của thành phố Hồ Chí Minh nơi mà Hoà và Thân hẹn gặp. (các số cách nhau ít nhất 1 khoảng cách)
- Dòng thứ i (1 ( i ( N - 1), trong N-1 dòng tiếp theo cho biết có hay không đường bay nối thành phố i với thành phố j (j=N-j+1) bằng các số 0, 1 (số 0 nghĩa là không có đường bay giữa hai đỉnh i , j; số 1 nghĩa là tồn tại đường bay giữa hai đỉnh i , j) các số cách nhau ít nhất 1 khoảng cách.
Ví dụ:
GAPNHAU.INP

9 6 2 7
1 0 1 1 1 0 0 0
1 1 0 0 0 0 0
0 0 0 1 0 0
0 1 1 0 0
0 0 0 0
0 0 0
0 0
1











- Dòng 0: 9 6 2 7 - Có 9 đỉnh mã số từ 1 đến 9, cần tìm đường đi từ đỉnh 6 đến đỉnh 7 và từ đỉnh 2 đến đỉnh 7.
- Dòng 1: 1 0 1 1 1 0 0 0 - đỉnh 1 được nối với các đỉnh 2, 4, 5, và 6. Không có cạnh nối đỉnh 1 với các đỉnh 3, 7, 8 và 9.
- Dòng 2: 1 1 0 0 0 0 0 - đỉnh 2 được nối với các đỉnh 3 và 4. Không có cạnh nối đỉnh 2 với các đỉnh 5, 6, 7,