编程介的小学生 2019-12-05 23:55 采纳率: 20.5%
浏览 80

Tree Fence

Problem Description
XEN has a small yard. The yard is square and 1000*1000 large. The lower left corner has coordinates (0, 0), the upper right (1000, 1000). There are N trees in the yard. In order to protect them, XEN wants to fence some of them.

XEN can only select some of the M positions which are provided in advance to insert wood piles, then he built fence along the inserted wood piles. Finally, the fence will be a polygon. As the picture below (Data is in the Sample):

XEN should pay 47 yuan for each wood pile which were inserted. But he can get 173 yuan from each tree which is in the final polygon. Obviously,the income is the difference between the total money he get and the total money he pay.

Now XEN want to know the maximum income he will get. But he doesn't know how to calculate it so that he asks your perfect team for help. Can you help him?

Input
Your program is to read from standard input.

In the first line, there are two integer N, M (1 ≤ N, M ≤ 200), as the description means. The following lines are in the format: the former N lines are the locations of trees, the other M lines are for the M positions. In addition, there is a space between the two numbers of the same line.

Tx1 Ty1
Tx2 Ty2
...
Txn Tyn
Px1 Py1
Px2 Py2
...
PXm Pym

(0 ≤ Txi, Tyi, Pxi, Pyi ≤ 1000, Integer!)

Output
Output an integer, the maximum income, in one line (enter is needed).

Sample Input
3 4
400 300
600 500
800 900
800 300
200 200
200 700
600 700

Sample Output
205

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 oracle集群安装出bug
    • ¥15 关于#python#的问题:自动化测试
    • ¥20 问题请教!vue项目关于Nginx配置nonce安全策略的问题
    • ¥15 教务系统账号被盗号如何追溯设备
    • ¥20 delta降尺度方法,未来数据怎么降尺度
    • ¥15 c# 使用NPOI快速将datatable数据导入excel中指定sheet,要求快速高效
    • ¥15 再不同版本的系统上,TCP传输速度不一致
    • ¥15 高德地图点聚合中Marker的位置无法实时更新
    • ¥15 DIFY API Endpoint 问题。
    • ¥20 sub地址DHCP问题