Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TFIELD - VOI 2015 Day 1 - Ruộng bậc thang

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/tfield


Ở các vùng cao hiếm đất cùng mặt bằng để canh tác, khi tiến hành trồng trọt trên các sườn đồi núi có đất màu, người ta phải bạt tam cấp để tạo thành những vạt đất bằng. Khu vực đất dốc dùng để canh tác như vậy gọi là ruộng bậc thang. Hình ảnh các khu ruộng bậc thang vẫn luôn là một hình ảnh đẹp ở các vùng cao khiến du khách và các nhà nhiếp ảnh đam mê và tốn không ít phim ảnh. Gia đình Hoàng có một khu ruộng bậc thang bao quanh một ngọn đồi được chia thành các khoang bậc thang, mỗi khoang trồng một loại cây. Khi nhìn từ trên cao xuống, ta thấy các khoang bậc thang này có hình dạng của các đa giác lồi lồng nhau. Ngoại trừ khoang chứa đỉnh đồi có biên là một đa giác lồi chứa đỉnh đồi, mỗi khoang còn lại được xác định bởi hai đa giác lồng nhau: đa giác có diện tích lớn hơn được gọi là biên ngoài của khoang còn đa giác có diện tích nhỏ hơn được gọi là biên trong của khoang. Mỗi khoang có màu đặc trưng của loại cây được trồng ở khoang đó. Vốn là một người say mê chụp ảnh, muốn có một bức ảnh đẹp, Hoàng tìm cách thay đổi không quá k loại cây được trồng ở k khoang để khi nhìn từ trên cao xuống sẽ thấy một vùng cùng màu có diện tích lớn nhất. Hoàng đã ghi nhận được danh sách m đa giác lồi mô tả biên ngoài của m khoang và màu tương ứng của chúng. Do sơ xuất, Hoàng đã để các thông tin về các khoang trong danh sách bị xáo trộn, không còn được liệt kê theo đúng trình tự từ khoang trong đến khoang ngoài.

Yêu cầu: Cho biết thông tin về danh sách mà Hoàng đã ghi nhận và số nguyên k, hãy tìm cách thay đổi không quá k loại cây được trồng ở k khoang để khi nhìn từ trên cao xuống sẽ thấy một vùng cùng màu có diện tích lớn nhất.

Dữ liệu vào:

  • Dòng đầu chứa hai số nguyên dương m, k (k m);
  • Dòng thứ i trong số m dòng tiếp theo chứa thông tin về khoang thứ i trong danh sách mà Hoàng ghi nhận bao gồm:
    • Đầu tiên là số nguyên ni là số đỉnh của đa giác lồi mô tả biên ngoài của khoang;
    • Tiếp theo là số nguyên ci thể hiện màu của khoang (1 ≤ ci m);
    • Cuối cùng là ni cặp số nguyên, mỗi số có trị tuyệt đối không quá 109, là tọa độ của một đỉnh của đa giác. Các đỉnh của đa giác được liệt kê theo thứ tự ngược chiều kim đồng hồ.

Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách.

Dữ liệu ra:

  • Ghi ra một số thực là diện tích vùng cùng màu lớn nhất sau khi thay đổi không quá k loại cây được trồng ở k khoang (kết quả đưa ra với độ chính xác 1 chữ số sau dấu chấm thập phân).

Ràng buộc:

  • Có 40% số test ứng với 40% số điểm của bài thỏa mãn điều kiện: m ≤ 10; k = 1; các đa giác mô tả biên ngoài của các khoang là hình chữ nhật;
  • Có 40% số test khác ứng với 40% số điểm của bài thỏa mãn điều kiện: m ≤ 10; các đa giác mô tả biên ngoài của các khoang là tam giác;
  • Có 20% số test còn lại ứng với 20% số điểm của bài thỏa mãn điều kiện: mni ≤ 1000.

Ví dụ:

Input:
3 1
4 1 0 0 1 0 1 1 0 1
4 1 -2 -3 5 -3 5 5 -2 5
3 2 -1 -1 4 -1 -1 4

Output:
56.0

Được gửi lên bởi:VOJ Team
Ngày:2015-01-13
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:VOI15 day 1

hide comments
2016-10-17 02:18:09
Duyệt trâu cũng ac
2016-09-29 03:57:29 minhsn
trau k ac dau may pn ui
2016-05-12 12:11:22
Đề quốc gia năm ngoái hay quá, chả bù năm nay....
2016-02-09 15:19:44 xin đừng quên tôi
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI: http://yeulaptrinh.pw/22/spoj-tfield/

Last edit: 2016-12-02 14:45:14
2015-10-31 10:29:47 The Legendary Tiger (NDHD)
Hình học + sort + duyệt

Last edit: 2015-10-31 10:33:47
2015-10-08 12:13:39
có ai 94 điểm ko? :'( buồn quá đê
2015-09-02 15:42:44
bài này hay @@
2015-09-02 11:28:58
sao 74 mãi vậy trời :'(
2015-03-30 21:54:11 ChienTran


Last edit: 2015-11-28 15:42:29
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.