Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
5. Nhóm hình đồng dạng In E-mail
(6 votes)
Người viết: Ngô Minh Đức   
27/03/2008

Trên mặt phẳng cho K hình, đánh số thứ tự từ 1 đến K. Mỗi hình tạo bởi một đường gấp khúc khép kín không tự cắt có các cạnh song song với các trục tọa độ.

Ta nói hai hình là thuộc cùng một nhóm đồng dạng nếu bằng cách thực hiện các phép biến đổi: lấy đối xứng qua trục, xoay, tịnh tiến song song với trục tọa độ, phóng to, thu nhỏ đối với một hình có thể đặt nó trùng khít lên hình kia.

Yêu cầu: Xác định số lượng nhóm đồng dạng và số lượng hình trong mỗi nhóm tìm được.


Dữ liệu

  • Dòng đầu tiên ghi số nguyên K là số lượng hình.
  • Dòng thứ i trong K dòng tiếp theo mô tả hình thứ i: đầu tiên là ki (4 ≤ ki ≤ 200) là số luợng đỉnh của hình thứ i (1 ≤ i ≤ K), tiếp theo là ki cặp tọa độ của các đỉnh được liệt kê theo một chiều đi vòng quanh hình (các tọa độ là các số nguyên có trị tuyệt đối không quá 20000).

Các số trên cùng một dòng được ghi cách nhau một dấu cách.

Kết qủa

  • Dòng đầu tiên ghi số nguyên M là số lượng nhóm hình đồng dạng tìm được.
  • Dòng thứ hai ghi dãy M số nguyên là dãy số lượng các phần tử của các nhóm được liệt kê theo thứ tự không giảm.

Giới hạn

  • Trong tất cả các test: 1 ≤ K ≤ 200.
  • Có 50% số lượng test với K ≤ 100.

Ví dụ

<strong>Dữ liệu:</strong>
6
6 -2 8 -1 8 -1 7 1 7 1 5 -2 5
12 2 5 3 5 3 0 2 0 2 1 1 1 1 2 0 2 0 3 -1 3 -1 4 2 4
6 7 -2 4 -2 4 0 6 0 6 1 7 1 
6 10 6 12 6 12 8 6 8 6 2 10 2
12 1 -1 1 -2 0 -2 0 -3 -1 -3 -1 -4 -2 -4 -2 -5 3 -5 3 -4 2 -4 2 -1
6 8 -1 8 -4 11 -4 11 -3 10 -3 10 -1
 
<strong>Kết qủa</strong>
2
2 4

 
< Trước   Tiếp >