TAILIEUCHUNG - 150 Bài Toán Tin Đại học Sư Phạm Hà Nội 2004 – 2006 phần 4

043. PHÂN HO CH TAM GIÁC Xét một đa giác lồi với n cạnh, các đỉnh được đánh số theo thứ tự từ 1 tới n. Một bộ n - 3 đường chéo đôi một không cắt nhau sẽ chia đa giác đã cho thành n - 2 tam giác. Ta gọi bộ gồm n - 3 đường chéo đó là một phép tam giác phân của đa giác lồi ban đầu. Trọng số của một phép tam giác phân là tổng độ dài các đường chéo được sử dụng trong phép phân hoạch. Yêu cầu: . | 043. PHÂN HOẠCH TAM GIÁC Xét một đa giác lồi với n cạnh các đỉnh được đánh số theo thứ tự từ 1 tới n. Một bộ n - 3 đường chéo đôi một không cắt nhau sẽ chia đa giác đã cho thành n - 2 tam giác. Ta gọi bộ gồm n - 3 đường chéo đó là một phép tam giác phân của đa giác lồi ban đầu. Trọng số của một phép tam giác phân là tổng độ dài các đường chéo được sử dụng trong phép phân hoạch. Yêu cầu Cho trước một đa giác lồi hãy tìm một phép tam giác phân nhỏ nhất có trọng số nhỏ nhất Dữ liệu Vào từ file văn bản . Trong đó Dòng 1 Ghi số đỉnh n của đa giác đã cho n dòng tiếp theo dòng thứ i gồm 2 số thực Xi Yi theo thứ tự là hoành độ và tung độ của đỉnh thứ i. Các đỉnh được liệt kê theo đúng thứ tự gọi tên đa giác Kết quả Ghi ra file văn bản . Trong đó Dòng 1 Ghi trọng số của phép tam giác phân nhỏ nhất n - 3 dòng tiếp theo mỗi dòng ghi hai số nguyên dương i j cho biết có sử dụng đường chéo nối đỉnh i với đỉnh j trong phép phân hoạch tìm được Các số trên một dòng của Input Output file được ghi cách nhau ít nhất một dấu cách. Giới hạn 1. n nguyên dương 4 n 100 2. Các toạ độ đỉnh là số thực Xi I I Yi I 106 3. Trọng số của phép tam giác phân nhỏ nhất được ghi dưới dạng số thực làm tròn lấy 6 chữ số sau dấu chấm thập phân. Ví dụ 6 4 0 2 6 5 1 2 4 6 4 4 6 2 4 0 3 2 1 53 044. CÁC THÀNH PHẦN LIÊN THÔNG MẠNH Cho đồ thị có hướng G V E gồm n đỉnh và m cung. Một đồ thị con G của G được gọi là một thành phần liên thông mạnh nếu hai điều kiện sau thoả mãn 1. Hoặc G chỉ gồm 1 đỉnh hoặc với hai đỉnh i j bất kỳ của G luôn tồn tại đường đi từ đỉnh i tới đỉnh j. 2. Việc thêm vào G một đỉnh bất kỳ sẽ làm hỏng tính chất 1 Yêu cầu Cho biết số thành phần liên thông mạnh của đồ thị đã cho và liệt kê tất cả các thành phần liên thông mạnh. Dữ liệu Vào từ file văn bản trong đó Dòng 1 Ghi hai số n m m dòng tiếp theo mỗi dòng ghi hai số nguyên dương x y thể hiện có cung nối từ đỉnh x tới đỉnh y Kết quả Ghi ra file văn bản trong đó .

TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.