CẮT HÌNH

Nguồn: Bắc bộ 2015

Một mảnh giấy hình chữ nhật được cắt bởi những nhát kéo. Cho biết toạ độ của mảnh giấy cũng như các nhát cắt, hãy xác định số mảnh được cắt rời.

Giả thiết mảnh giấy được đặt trong một hệ toạ độ sao cho các mép giấy song song với các trục toạ độ, góc dưới trái của nó trùng với điểm (0; 0) và góc trên phải của nó trùng với điểm (m; n). Mỗi nhát cắt được xác định bởi hai đầu mút trên biên của mảnh giấy sao cho đảm bảo đoạn thẳng nối hai đầu mút này thực sự cắt mảnh giấy.

Dữ liệu vào cho trong file văn bản CAT.INP gồm:

·         dòng đầu ghi hai giá trị m và n (m, n nguyên dương, m,n < 10³)

·         dòng tiếp theo ghi số nhát cắt.

·         các dòng tiếp theo, mỗi dòng ghi toạ độ của một nhát cắt gồm 4 số: 2 số đầu là hoành độ và tung độ của một đầu mút và 2 số sau là hoành độ và tung độ của đầu mút còn lạ.

Các toạ độ trong file dữ liệu đều là những số nguyên và được ghi cách nhau ít nhất một dấu trắng nếu trên cùng một dòng. Giới hạn số nhát cắt không quá 300.

Kết quả ghi ra file văn bản CAT.OUT số mảnh bị cắt rời.

Ví dụ hình vẽ trên mô tả một mảnh giấy bị cắt bởi 6 nhát kéo thành 13 mảnh, tương ứng với các file vào, ra dưới đây:

CAT.INP		CAT.OUT
10 10 6 3    10   0     9 8    0     3     10 0    0     10   2 0    8     10   6 9    10    4     0 10   6    0      1		13

 Test - Solution - Đề (word)

CHIA ĐẤT

Một người cha khi mất đi để lại một mảnh đất có hình dạng là một đa giác lồi làm của thừa kế cho hai người con của mình. Trong di chúc ông yêu cầu rằng hai người con phải chia mảnh đất này thành hai phần có diện tích bằng nhau theo một đường ranh giới thẳng dọc theo phương Nam - Bắc. Bạn là người được giao giúp hai người con thực hiện bản di chúc này. Hãy viết chương trình tìm cách chia.

Giả sử mảnh đất là đa giác lồi với các đỉnh là A₁A₂....A_n nằm trên mặt phẳng toạ độ còn trục Oy nằm theo hướng Nam - Bắc, Ox theo hướng Tây - Đông.

Dữ liệu vào: từ tệp văn bản CHIADAT.INP

+ Dòng đầu tiên ghi N là số đỉnh của đa giác (N≤5000)

+ Trong N dòng tiếp theo, dòng thứ i ghi hai số nguyên x_i, y_i lần lượt là hoành độ và tung độ của điểm thứ i trong số N đỉnh đa giác (các đỉnh của đa giác được liệt kê theo chiều xuôi hoặc ngược kim đồng hồ)

Dữ liệu ra: Ghi ra file văn bản CHIADAT.OUT một số thực x₀ với ý nghĩa đường ranh giới dùng để chia đất là đường thẳng x=x₀ (x₀ viết với 4 chữ số phần thập phân)

Ví dụ:

CHIADAT.INP	CHIADAT.OUT
4 0  0 2  0 2  2 0  2	1.0000

SOLUTION

KHÔI PHỤC ĐA GIÁC

Bờm vẽ trên mặt phẳng một hình đa giác tổng quát (đường gấp khúc khép kín không tự cắt) với các cạnh song song với các trục tọa độ và các đỉnh có tọa độ nguyên. Sau đó vì vô ý Bờm đã xóa mất tất cả các cạnh đứng (song song với trục tung) của đa giác. Bạn hãy tìm cách từ những thông tin còn lại trên hình vẽ giúp Bờm tính diện tích của đa giác ban đầu.

Dữ liệu vào: từ tệp văn bản POLYGON.INP

+ Dòng đầu tiên chứa N là số cạnh nằm ngang (cạnh song song với trục hoành) của đa giác đã cho (N≤1000)

+ Mỗi dòng trong số N dòng tiếp theo chứa thông tin về một cạnh nằm ngang của đa giác bao gồm 4 số nguyên x, y, u, v được ghi cách nhau bởi dấu cách, trong đó (x,y) và (u,v) là hai cặp tọa độ của hai đầu mút của cạnh nằm ngang. Giả thiết rằng các tọa độ là các số nguyên có giá trị tuyệt đối không quá 100.

Dữ liệu ra: ghi vào tệp văn bản POLYGON.OUT

+ Dòng đầu tiên ghi diện tích của đa giác                       

+ Dòng thứ i trong số 2*N dòng tiếp theo chứa tọa độ đỉnh thứ i của đa giác được liệt kê theo thứ tự đi vòng quanh đa giác theo chiều kim đồng hồ (đỉnh bắt đầu được chọn tùy ý)

Ví dụ:

POLYGON.INP	POLYGON.OUT
2 1 1 3 1 1 3 3 3	4 1 1 1 3 3 3 3 1

SOLUTION