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.|

MIDAS - Vua Midas thích vàng

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/midas


Trong thần thoại Hy Lạp, do có công giúp đỡ người thầy của thần Dyonysus, nhà vua Midas được vị thần thưởng cho bằng cách đưa ngài đến một hòn đảo có dạng một đa giác lồi N cạnh. Hòn đảo đã được chia thành các vùng bởi M đường rào là các đoạn thẳng nối một số cặp đỉnh của đa giác. Biết rằng các đoạn rào chỉ có điểm chung tại các đầu mút (các đỉnh).
Thần Dyonysus nói với Midas rằng, nhà vua có thể chọn K mảnh bất kì trong số các mảnh đã được tạo ra bởi đường biên của đảo và các đường rào, miễn sao K mảnh đó phải ghép lại thành một miền liên tục.
Yêu cầu: Hãy giúp vua Midas tham lam chọn ra K mảnh sao cho miền thu được có diện tích lớn nhất.

Input

Dòng đầu tiên ghi 3 số nguyên dương N, M, K (K ≤ M ≤ 100, N ≤ 1000).
N dòng tiếp theo, dòng thứ i ghi hai số nguyên xi, yi ( |xi|, |yi| <= 1000000) là tọa độ của đỉnh thứ i của đa giác lồi (theo chiều ngược kim đồng hồ).
Cuối cùng là M dòng, mỗi dòng mô tả một đường rào, gồm 2 số u, v cho biết đường rào nối hai đỉnh u và v.

Output

1 Dòng duy nhất ghi S là diện tích lớn nhất tìm được, chính xác đến 2 chữ số sau dấu phẩy.

Example

Input:
8 4 2
0 0
0 2
1 4
3 5
5 5
6 4
6 2
4 0
1 3
3 8
4 7
4 8

Output:
13.50

Được gửi lên bởi:Nguyen Minh Hieu
Ngày:2007-02-02
Thời gian chạy:0.100s
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 ERL GOSU JS-RHINO NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:Mr Tran Quang Khai

hide comments
2017-12-26 17:07:01
ghê
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.