1077 - The Sky is the Limit

发布时间:2014-10-22 13:02:35编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"1077 - The Sky is the Limit",主要涉及到1077 - The Sky is the Limit方面的内容,对于1077 - The Sky is the Limit感兴趣的同学可以参考一下。

The city of Banff hired an advertising agency to promote the city's attractions to potential visitors. One of the planned slogans stated that the mountain ranges around the city form the most beautiful skyline in Canada. But the Institute for Consumer Protection in Canada (ICPC) decided that ``the most beautiful skyline" was a subjective and unverifiable claim, and could therefore be considered misleading. The advertising agency then came up with the slogan ``Banff - the longest skyline in Canada." Although not as catchy, it is hopefully verifiable, and therefore admissible under Canada's tricky advertising laws. This is where you come in. What the advertising agency needs is a program that determines the length of a skyline. Consider each mountain as a two-dimensional triangle having two upper sides the same length. A skyline is the outline of one or more mountains. The skyline's length is the total length of the outline. The left illustration below shows three mountains. The right illustration shows (with bold lines) the skyline and (with dashed lines) the portion of the mountains' upper edges that are not part of the skyline. Note that parts of the horizon line that lie between mountains are not considered part of the skyline. Input  Each input file contains one or more test cases, which are descriptions of mountain ranges. Each description starts with a line containing a positive integer N , which specifies the number of mountains in the range. Each of the next N lines describes a mountain with three integers X , H , and B , which specify the horizontal position of the mountain's peak relative to some fixed point, the height of the peak, and the width of the base of the mountain, respectively. The base of each mountain coincides with a horizontal line. The values satisfy the conditions N100 , H > 0 , and B > 0 . The last test case is followed by a line containing a zero. Output  For each test case, print the case number (beginning with 1) and the length of the skyline. Print the length rounded to the nearest integer, with 0.5 rounded up. Print a blank line after the output of each test case. Use the format shown in the sample output below. Sample Input  1 100 50 100 3 20 30 35 37 24 29 60 20 13 0 Sample Output  Case 1: 141 Case 2: 138 #include<stdio.h> #include<math.h> #include<algorithm> using namespace std; const int maxn=111; const int maxpoints=11111; const double eps=1e-9; int n,i,j,points,id[maxpoints],cases; double x[maxn],h[maxn],b[maxn],point[maxpoints],left,right,mid,top,side,k,height,len; void addpoints(double z) { point[points]=z; id[points]=points; points++; } void cross(double xa,double xb,double yb,double xc,double xd,double yd) { double va,vc,t; va=(xb-xa)/yb;vc=(xd-xc)/yd; if(fabs(va-vc)<1e-9) return; t=(xc-xa)/(va-vc); if(t>0&&t<yb&&t>yd) addpoints(xa+va*t); } bool cmp(int i,int j) { return point[i]<point[j]; } int main() { while(scanf("%d",&n)&&n) { points=0; for(i=0;i<n;i++) { scanf("%lf%lf%lf",&x[i],&h[i],&b[i]); b[i]/=2; addpoints(x[i]-b[i]); addpoints(x[i]); addpoints(x[i]+b[i]); for(j=0;j<i;j++) { cross(x[i]-b[i],x[i],h[i],x[j]-b[j],x[j],h[j]); cross(x[i]+b[i],x[i],h[i],x[j]-b[j],x[j],h[j]); cross(x[i]-b[i],x[i],h[i],x[j]+b[j],x[j],h[j]); cross(x[i]+b[i],x[i],h[i],x[j]+b[j],x[j],h[j]); } } sort(id,id+points,cmp); len=0; for(i=1;i<points;i++) { left=point[id[i-1]]; right=point[id[i]]; mid=(left+right)/2; if(right-left>eps) { top=-2; for(j=0;j<n;j++) { side=x[j]-b[j]; if(side<mid&&x[j]>mid) { height=h[j]*(mid-side)/b[j]; if(height>top) { top=height; k=h[j]/b[j]; } } side=x[j]+b[j]; if(x[j]<mid&&side>mid) { height=h[j]*(side-mid)/b[j]; if(height>top) { top=height; k=h[j]/b[j]; } } } if(top>-1) len+=(right-left)*sqrt(1+k*k); } } printf("Case %d: %d\n\n",++cases,((int)((len+0.5)*10))/10); } return 0; }

下一篇:基于MTD的NANDFLASH设备驱动底层实现原理分析(三) .