来自 情感专区 2019-10-04 20:23 的文章
当前位置: 金沙城娱乐官方平台 > 情感专区 > 正文

金沙澳门官网官方网站长富问候

风车 载历史的货物 和太阳 赛跑 身后的寂静、车辙 拔取心中的 枯草 去年的冬 无处落脚 / 17年的阳光 来得这么早 这么赤城 我清空所有的记忆 呆呆的站在路边 忘了身边 被拉得长长的困扰 / 季节的脚步 迟滞空中 阳光打乱 我的罗盘 苍白的背影 裹挟风中 / 17年的阳光 没忘记寒冷的骨头 早早地奔赴风口 瞭望残雪 何在 瞭望寒冬 出口 / 披挂全新的 17年阳光 伴随钟声 退步而去 不是留念 它只是串了 一串红灯笼 从万家楼台 输入 输入 新的一年 真诚的问候

题目描述

致力于建设全国示范和谐小村庄的H村村长dadzhi,决定在村中建立一个瞭望塔,以此加强村中的治安。

我们将H村抽象为一维的轮廓。如下图所示

金沙澳门官网官方网站 1

我们可以用一条山的上方轮廓折线(x1, y1), (x2, y2), …. (xn, yn)来描述H村的形状,这里x1 < x2 < …< xn。瞭望塔可以建造在[x1, xn]间的任意位置, 但必须满足从瞭望塔的顶端可以看到H村的任意位置。可见在不同的位置建造瞭望塔,所需要建造的高度是不同的。为了节省开支,dadzhi村长希望建造的塔高度尽可能小。

请你写一个程序,帮助dadzhi村长计算塔的最小高度。

版权作品,未经《短文学》书面授权,严禁转载,违者将被追究法律责任。

输入输出格式

输入格式:

输入文件tower.in第一行包含一个整数n,表示轮廓折线的节点数目。接下来第一行n个整数, 为x1 ~ xn. 第三行n个整数,为y1 ~ yn。

输出格式:

输出文件tower.out仅包含一个实数,为塔的最小高度,精确到小数点后三位。

输入输出样例

输入样例#1: 复制

6
1 2 4 5 6 7
1 2 2 4 2 1

输出样例#1: 复制

1.000

说明

对于60%的数据, N ≤ 60;

对于100%的数据, N ≤ 300,输入坐标绝对值不超过106,注意考虑实数误差带来的问题

这题分两步。第一步就是求出满足条件的半平面,这半部分就是"水平可见直线"那题。

第二部就是计算答案。可以证明瞭望塔的横坐标一定在半平面或地面的拐点处,因为中间部分一定没有其中一端优秀。

所以对半平面和地面的拐点分别拎出来讨论一下就好了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 struct Line
 8 {
 9   double k,b;
10 }line[10001],sta[10001];
11 int n,top;
12 double x[1002],y[1001],inf=1e8,eps=1e-10,ans=2e12;
13 int dcmp(double X)
14 {
15   if (X>eps) return 1;
16   if (X<-eps) return -1;
17   return 0;
18 }
19 double getx(Line a,Line b)
20 {
21   return ((b.b-a.b)/(a.k-b.k));
22 }
23 double gety(double X)
24 {int i;
25   for (i=1;i<=n;i++)
26     {
27       if (x[i+1]>=X) break;
28     }
29   if (i==n+1) return -inf;
30   double k=(y[i+1]-y[i])/(x[i+1]-x[i]),b=y[i]-k*x[i];
31   return X*k+b;
32 }
33 bool cmp(Line a,Line b)
34 {
35   if (dcmp(a.k-b.k)==0)
36     return a.b<b.b;
37   return a.k<b.k;
38 }
39 int main()
40 {
41   int i,j;
42   double maxx;
43   cin>>n;
44   for (i=1;i<=n;i++)
45     scanf("%lf",&x[i]);
46   for (i=1;i<=n;i++)
47     scanf("%lf",&y[i]);
48   for (i=1;i<=n-1;i++)
49     {
50       line[i].k=(y[i+1]-y[i])/(x[i+1]-x[i]);
51       line[i].b=y[i]-line[i].k*x[i];
52     }
53   n--;
54   sort(line+1,line+n+1,cmp);
55   line[n+1].k=inf;
56   sta[1]=line[1];sta[2]=line[2];
57   top=2;
58   for (i=3;i<=n;i++)
59     {
60       if (dcmp(line[i].k-line[i+1].k)==0)
61     continue;
62       while (top>1&&getx(line[i],sta[top-1])<=getx(sta[top],sta[top-1])) top--;
63       top++;
64       sta[top]=line[i];
65     }
66   for (i=1;i<top;i++)
67     {
68       double X=getx(sta[i],sta[i+1]);
69       double Y=sta[i].k*X+sta[i].b;
70       if (dcmp(Y-gety(X))>=0)
71       ans=min(ans,Y-gety(X));
72     }
73   for (i=1;i<=n+1;i++)
74     {
75       maxx=0;
76       for (j=1;j<=top;j++)
77     {
78       maxx=max(maxx,x[i]*sta[j].k+sta[j].b);
79     }
80       if (dcmp(maxx-y[i])>=0)
81       ans=min(ans,maxx-y[i]);
82     }
83   printf("%.3lfn",ans);
84 }

 

本文由金沙城娱乐官方平台 发布于情感专区,转载请注明出处:金沙澳门官网官方网站长富问候

关键词: