Cho hai đa giác A và B,theo định nghĩa tổng Minkowski của A và B bao gồm tất cả các điểm có dạng (x1+x2, y1+y2) trong đó (x1,y1) là một điểm nằm trong đa giác A và (x2,y2) là một điểm nằm trong đa giác B. Người ta chứng minh được rằng tổng Minkowski của các đa giác cũng là một đa giác. Hình dưới đây là một ví dụ: Hai tam giác và tổng Minkowski của chúng.

Chúng ta sẽ xem xét tính đảo ngược của tổng Minkowski. Cho một đa giác P, tìm hai đa giác A và B sao cho:
- P là tổng Minkowski của hai đa giác A và B.
- A được tạo từ 2 đến 4 đỉnh khác nhau, ví dụ là một đoạn thẳng (gồm hai đỉnh), một tam giác (3 đỉnh) hoặc một tứ giác (4 đỉnh),
- A phải là hình có nhiều đỉnh nhất nếu có thể, nghĩa là:
+ Nếu có thể là tứ giác thì A phải là một tứ giác,
+ Trong trường hợp A không là tứ giác, thì nếu có thể A phải là một tam giác,
+ Các trường hợp còn lại A là một đoạn thẳng.

Rõ ràng rằng đa giác A hoặc B đều không thể là đa giác P bởi vì nếu như vậy A hoặc B sẽ chỉ một điểm, điểu này mâu thuẫn với định nghĩa đa giác của chúng ta.

Cho một tập file input, mỗi một file chứa mô tả một đa giác P. Với mỗi file input bạn hãy tìm 2 đa giác A và B thoả mãn điều kiện ở trên và đưa vào file Output. Mỗi một file Input chúng ta sẽ luôn tìm được hai đa giác A và B. Nếu có nhiều phương án đúng, bạn chỉ cần tìm ra một trong số chúng.

INPUT
Bạn nhận được 10 ví dụ trong các file text được đánh tên từ polygon1.in đến polygon10.in. Mỗi một file input được tổ chức theo cách sau. Dòng đầu tiên chứa một số nguyên N: là số đỉnh của đa giác P. N dòng tiếp theo mô tả các đỉnh theo hướng ngược chiều kim đồng hồ, mỗi một đỉnh trên một dòng. Dòng thứ i+1 (i=1..N) chứa hai số nguyên xi,yi cách nhau bởi khoảng trắng là toạ độ thứ i của đa giác. Toạ độ trong tất cả các file input đều nguyên không âm.
OUTPUT
Bạn phải đưa ra 10 file Output tương ứng với 10 file input đã cho. Mỗi một file mô tả đa giác A và B.
- Dòng đầu tiên ghi #FILE polygon i trong đó i (1≤ i ≤10) là số tự nhiên tương ứng trong file input.
- Dòng thứ hai chứa một số nguyên NA: là số đỉnh của đa giác A (2 ≤NA ≤4).
- NA dòng tiếp theo mô ta đỉnh của đa giác A theo hướng ngược chiều kim đồng hồ. Dòng i+2 (i=1,2,..,NA) chứa hai số nguyên X, Y ngăn cách nhau bởi khoảng trắng là toạ độ của đỉnh thứ i của đa giác A.
- Dòng NA+3 chứa một số nguyên NB: là số đỉnh của đa giác B (2 ≤ NB ≤ 4).
- NB dòng tiếp theo mô tả các đỉnh của đa giác B theo hướng ngược chiều kim đồng hồ.
- Dòng thứ NA+j+3 với j=1,2,..NB chứa hai số nguyên x,y ngăn cách nhau bởi khoảng trắng là toạ độ đỉnh thứ j của đa giác B.

Ví dụ

Với file input trên, file output có thể là một trong hai trường hợp dưới đều đúng vì trong cả hai trường hợp A đều là tam giác nó không thể là tứ giác.

Người viết: Ngô Minh Đức
10/04/2008
Strict Standards: Non-static method HTML_content::TOC() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 526 Bài toán Đa giác Một đa giác gồm có các điểm và các cạnh. Một đa giác lồi có đặc điểm là đường thẳng nối hai đỉnh bất kỳ bao giờ cũng nằm trong đa giác. Tất cả các đa giác trong bài toán này đều lồi và có ít nhất hai đỉnh,tất cả các đỉnh thì khác nhau và đều có toạ độ nguyên. Không có ba đỉnh nào nằm trên cùng một đường thẳng. Từ "đa giác" dưới đây luôn luôn mô tả một đa giác lồi như vậy. Cho hai đa giác A và B,theo định nghĩa tổng Minkowski của A và B bao gồm tất cả các điểm có dạng (x1+x2, y1+y2) trong đó (x1,y1) là một điểm nằm trong đa giác A và (x2,y2) là một điểm nằm trong đa giác B. Người ta chứng minh được rằng tổng Minkowski của các đa giác cũng là một đa giác. Hình dưới đây là một ví dụ: Hai tam giác và tổng Minkowski của chúng. Chúng ta sẽ xem xét tính đảo ngược của tổng Minkowski. Cho một đa giác P, tìm hai đa giác A và B sao cho: - P là tổng Minkowski của hai đa giác A và B. - A được tạo từ 2 đến 4 đỉnh khác nhau, ví dụ là một đoạn thẳng (gồm hai đỉnh), một tam giác (3 đỉnh) hoặc một tứ giác (4 đỉnh), - A phải là hình có nhiều đỉnh nhất nếu có thể, nghĩa là: + Nếu có thể là tứ giác thì A phải là một tứ giác, + Trong trường hợp A không là tứ giác, thì nếu có thể A phải là một tam giác, + Các trường hợp còn lại A là một đoạn thẳng. Rõ ràng rằng đa giác A hoặc B đều không thể là đa giác P bởi vì nếu như vậy A hoặc B sẽ chỉ một điểm, điểu này mâu thuẫn với định nghĩa đa giác của chúng ta. Cho một tập file input, mỗi một file chứa mô tả một đa giác P. Với mỗi file input bạn hãy tìm 2 đa giác A và B thoả mãn điều kiện ở trên và đưa vào file Output. Mỗi một file Input chúng ta sẽ luôn tìm được hai đa giác A và B. Nếu có nhiều phương án đúng, bạn chỉ cần tìm ra một trong số chúng. INPUT Bạn nhận được 10 ví dụ trong các file text được đánh tên từ polygon1.in đến polygon10.in. Mỗi một file input được tổ chức theo cách sau. Dòng đầu tiên chứa một số nguyên N: là số đỉnh của đa giác P. N dòng tiếp theo mô tả các đỉnh theo hướng ngược chiều kim đồng hồ, mỗi một đỉnh trên một dòng. Dòng thứ i+1 (i=1..N) chứa hai số nguyên xi,yi cách nhau bởi khoảng trắng là toạ độ thứ i của đa giác. Toạ độ trong tất cả các file input đều nguyên không âm. OUTPUT Bạn phải đưa ra 10 file Output tương ứng với 10 file input đã cho. Mỗi một file mô tả đa giác A và B. - Dòng đầu tiên ghi #FILE polygon i trong đó i (1≤ i ≤10) là số tự nhiên tương ứng trong file input. - Dòng thứ hai chứa một số nguyên NA: là số đỉnh của đa giác A (2 ≤NA ≤4). - NA dòng tiếp theo mô ta đỉnh của đa giác A theo hướng ngược chiều kim đồng hồ. Dòng i+2 (i=1,2,..,NA) chứa hai số nguyên X, Y ngăn cách nhau bởi khoảng trắng là toạ độ của đỉnh thứ i của đa giác A. - Dòng NA+3 chứa một số nguyên NB: là số đỉnh của đa giác B (2 ≤ NB ≤ 4). - NB dòng tiếp theo mô tả các đỉnh của đa giác B theo hướng ngược chiều kim đồng hồ. - Dòng thứ NA+j+3 với j=1,2,..NB chứa hai số nguyên x,y ngăn cách nhau bởi khoảng trắng là toạ độ đỉnh thứ j của đa giác B. Ví dụ Với file input trên, file output có thể là một trong hai trường hợp dưới đều đúng vì trong cả hai trường hợp A đều là tam giác nó không thể là tứ giác.