TZOJ 2569 Wooden Fence(凸包求周长)

时间:2022-10-07 12:45:39

描述

Did you ever wonder what happens to your money when you deposit them to a bank account? All banks hold such deposits in various assets, such as gold, stocks, obligations, deposits in other banks, loans, bonds, and many others. Due to the financial crisis and instability of the stock exchanges, many banks find out that stocks are not very reliable and their possession may be too risky.

Therefore, the banks now prefer other assets, especially gold. The main trouble with gold is that there is only a limited amount of it in the whole world. And it is not enough to cover all money held by all banks. (Wait, isn't this the real reason of the crisis?)

If there is not enough gold, other commodities must be exploited instead. The International Bank of Monetania (IBM) has recently come up with an idea of using very old and valuable trees as their assets. They bought a piece of land with several such trees and now expect their value to grow. Literally, of course.

Unfortunately, the trees are threatened by wildlife, because animals do not understand their value and nibble them. Moreover, there is a permanent danger of theft. As a result, it is absolutely necessary to build a good solid fence around the trees.

The IBM quickly realized that the only suitable material available to build the fence is the wood from the trees themselves. In other words, it is necessary to cut down some trees in order to build a fence around the remaining ones. Of course, to keep the maximum value, we want to minimize the value of the trees that had to be cut. You are to write a program that solves this problem.

输入

The input contains several test cases, each of which describes one piece of land. Each test case begins with a line containing a single integer N, 2 ≤ N≤ 16, the total number of trees. Each of the subsequent N lines contains 4 integers Xi, Yi, Vi, Li separated by at least one space.

The four numbers describe a single tree. (Xi, Yi) is the position of the tree in the plane, Vi is its value, and Li is the length of fence that can be built using the wood of the tree. You may assume that 0 ≤ Vi, Li ≤ 10000 and -10000 ≤ Xi, Yi ≤ 10000. No two trees in a test case will grow at the same position.

The input ends with a line containing zero in place of N.

输出

For each test case, compute a subset of the trees such that, using the wood from that subset, the remaining trees can be enclosed in a single continuous fence. Find the subset with the minimal total value. For simplicity, regard the trees as having zero diameter.

Output one line with the sentence "The lost value is T.", where T is the minimal value of the trees that must be cut.

样例输入

6
0 0 8 3
1 4 3 2
2 1 7 1
4 1 2 3
3 5 4 6
2 3 9 8
3
3 0 10 3
5 -3 20 25
7 -3 30 32
2
100 0 5 4
0 100 4 5
5
0 0 10 10
0 1 10 10
1 0 10 10
1 1 10 10
50 50 8 4
0

样例输出

The lost value is 9.
The lost value is 20.
The lost value is 4.
The lost value is 8.

题意

N棵树位置(X,Y)价值V长度L,要求砍伐的树价值最小并且总长度能围住剩下的树

题解

暴力凸包求周长,复杂度O(2^N*NlogN)

代码

 #include<bits/stdc++.h>
using namespace std; struct Point{
double x,y,V,L;
}d[],p[];
double dis(Point p1,Point p2){return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}
double xmulti(Point p1,Point p2,Point p0){return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}
double graham(int n)
{
int pl[],t=,num=;
for(int i=;i<=n;i++)if(p[i].y<p[t].y)t=i;
pl[]=t;
do
{
num++;
t=pl[num-]+;
if(t>n)t=;
for(int i=;i<=n;i++)
{
double x=xmulti(p[i],p[t],p[pl[num-]]);
if(x<)t=i;
}
pl[num]=t;
}while(pl[num]!=pl[]);
double sum=;
for(int i=;i<num;i++)
sum+=dis(p[pl[i]],p[pl[i+]]);
return sum;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF,n)
{
double minn=;
for(int i=;i<n;i++)scanf("%lf%lf%lf%lf",&d[i].x,&d[i].y,&d[i].V,&d[i].L),minn+=d[i].V;
int state=<<n;
for(int i=;i<state;i++)
{
int sxV=,sxL=,pos=;
for(int j=;j<n;j++)
{
if((i&(<<j))==)sxV+=d[j].V,sxL+=d[j].L;
else p[++pos]=d[j];
}
if(minn>sxV&&graham(pos)<=sxL)minn=sxV;
}
printf("The lost value is %.0f.\n",minn);
}
return ;
}

TZOJ 2569 Wooden Fence(凸包求周长)的更多相关文章

  1. zoj 1453 Surround the Trees(凸包求周长)

    链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=453 Time Limit: 2 Seconds      Memory ...

  2. hdu 1348 (凸包求周长)

    链接:http://acm.hdu.edu.cn/showproblem.php?pid=1348 Wall Time Limit: 2000/1000 MS (Java/Others)    Mem ...

  3. POJ 1113 Wall 凸包求周长

    Wall Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 26286   Accepted: 8760 Description ...

  4. Surround the Trees(凸包求周长)

    Surround the Trees Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Other ...

  5. HDU - 1392 凸包求周长&lpar;模板题&rpar;【Andrew】

    <题目链接> 题目大意: 给出一些点,让你求出将这些点全部围住需要的多长的绳子. Andrew算法 #include<iostream> #include<cstdio& ...

  6. HDU 4667 Building Fence&lpar;求凸包的周长&rpar;

    A - Building Fence Time Limit:1000MS     Memory Limit:65535KB     64bit IO Format:%I64d & %I64u ...

  7. &lpar;hdu step 7&period;1&period;7&rpar;Wall&lpar;求凸包的周长——求将全部点围起来的最小凸多边形的周长&rpar;

    题目: Wall Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Subm ...

  8. HDU1392Surround the Trees(凸包判断 &plus; 求周长)

    http://www.cnblogs.com/hmhard/archive/2013/02/05/2893035.html 这是判断三角区域那块写的不好. 判断凸包的方法: 1.将所有点按照y从小到大 ...

  9. poj 3348--Cows&lpar;凸包求面积&rpar;

    链接:http://poj.org/problem?id=3348 Cows Time Limit: 2000MS   Memory Limit: 65536K Total Submissions:  ...

随机推荐

  1. Android --Activity与Fragment通讯

    参考博客:详解Fragment跟Activity之间的通信 Activity中方法 private OnSearchListener mSearchListener; /** *定义一个借口 **/ ...

  2. JSBinding &plus; SharpKit &sol; 常见问题

    运行时出现: Return a "System.Xml.XmlIteratorNodeList" to JS failed. Did you forget to export th ...

  3. 简单Sql语句统计每年每个月的数据,每个月为数据的每列,简单SQL练习

    有一张表,数据如下 请写出结果为以下的SQL语句. 在mysql中创建表 CREATE TABLE `aa` (  `id` int(10) NOT NULL AUTO_INCREMENT COMME ...

  4. 两个java项目&comma;跨域访问时&comma;浏览器不能正确解析数据问题

    @Controller@RequestMapping(value = "api/item/cat")public class ApiItemCatController { @Aut ...

  5. Fastcgi、CGI 是什么

    1.CGI是干嘛的?CGI是为了保证web server传递过来的数据是标准格式的,方便CGI程序的编写者. 2.web server(比如说nginx)只是内容的分发者. 比如,如果请求/index ...

  6. 通过sql查找指定字段存在哪些表中

    select * from INFORMATION_SCHEMA.columns where COLUMN_NAME Like '%order_type%';

  7. VS Code 调试 Angular 和 TypeScript 的配置

    一.安装插件 在 Visual Studio Code 中打开扩展面板(快捷键 Ctrl+Shift+X),搜索安装 Debugger for chrome 插件). 二.配置启动参数 在 Visua ...

  8. git工具

    1.Git Bash常用命令: pwd    当前工作目录 clear   清屏 ls   列举当前目录下的文件及文件夹 cd 更改目录 mkdir   创建目录 touch   创建空文件 cp 拷 ...

  9. python 全栈开发,Day28&lpar;复习&comma;os模块&comma;导入模块import和from&rpar;

    一.复习 collections 增加了一些扩展数据类型 :namedtuple orderdict defaltdict队列和栈time 时间 三种格式 : 时间戳 结构化 字符串random 随机 ...

  10. CentOS7下Elastic Stack 5&period;0日志分析系统搭建

    原文链接:http://www.2cto.com/net/201612/572296_3.html 在http://localhost:5601下新建索引页面输入“metricbeat-*”,之后ki ...