首页 > ACM题库 > HDU-杭电 > HDU 4401-Battery-栈-[解题报告]HOJ
2015
05-24

HDU 4401-Battery-栈-[解题报告]HOJ

Battery

问题描述 :

Recently hzz invented a new kind of solar battery. The battery is so amazing that the electric power generated by it can satisfy the entire village. People in the villager are all very happy since they can get free and green energy from now on. But the manager of a power company is sorrow about this. So he plans to take some action to obstruct the battery.

The battery can be regarded as a segment of L meters. And the manager plans to build n pillars on the battery.

Mines

Like the picture above, the distance between pillar i and the battery’s left end is Xi, and its height is Hi. The thickness of all pillars can be ignored. When the sunlight is slant, some part of the battery will be sheltered by the pillars.

One meter battery exposed in the vertical sunlight for one hour will generate one unit of energy. If the sunlight is slant, the amount of energy generated should be multiplied by sinβ (β is the angle between sunlight and horizontal line).

The sun rises from the infinite far left end of the horizon at 6 o’clock and goes down at the infinite far right end of the horizon at 18 o’clock. The sun is always infinite far away. So the sunlight is parallel, and β is π/2 at 12 o′clock.

Please calculate the amount of energy generated by the battery between t1 o’clock and t2 o’clock (6 ≤t1<t2≤18 ).

输入:

There are multiple test cases.
For each test case:
The first line contains two integer L(10≤L≤100,000) andN(4≤N≤1000), indicating the length of the battery and the number of pillars.
The second line contains two integers, above mentioned t1 and t2(6 ≤t1<t2≤18 ).
Then N lines follow, each containing two integers Xi(0≤Xi≤L) and Hi(1≤Hi≤1000), indicating the position and height of a pillar.

It is guaranteed that no two pillars will be in the same position. It is also guaranteed that there is a pillar on both end of the battery.
The input end with L=0, N=0.

输出:

There are multiple test cases.
For each test case:
The first line contains two integer L(10≤L≤100,000) andN(4≤N≤1000), indicating the length of the battery and the number of pillars.
The second line contains two integers, above mentioned t1 and t2(6 ≤t1<t2≤18 ).
Then N lines follow, each containing two integers Xi(0≤Xi≤L) and Hi(1≤Hi≤1000), indicating the position and height of a pillar.

It is guaranteed that no two pillars will be in the same position. It is also guaranteed that there is a pillar on both end of the battery.
The input end with L=0, N=0.

样例输入:

10 4
14 17
0 2
5 1
8 3
10 1
0 0

样例输出:

7.97188

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4401

题意:给出一个长度为L的太阳能电池板。若阳光直射在板上,单位长度单位时间发电为1.斜射的话要乘以sin(x),x为阳光和地面夹角。求某一时间段太阳能电池板的发电量。

思路:

(1)

Battery

总的意思就是当前区间可能被之前的柱子挡住,我们将之前的柱子用一个单调栈保存,栈中从栈底到栈顶的柱子逐渐降低且连续两根的斜率的绝对值逐渐增大。求某一区间被哪些柱子挡住时只需要从栈顶向栈底扫描,这样就会将该区间依次划分为几段,依次计算即可;

(2)我是首先按照时间划分,而且将时间从[6,18]映射到[0,12],答案就是ans=deal(T2-6)-deal(T1-6)。设时间为t,若t小于等于6,则直接计算;若大于6,也就是下午还有一段,由于上午下午的对称性,与上午计算类似,设solve(t)表示计算在t<=6时,则若计算t>6时,就是solve(6)+[solve(6)-solve(12-t)],其中方括号里的为下午一段时间的;并且计算下午时要将数组的前后交换,你懂的。。。

(3)然后就是对于每一段的发电量就是一个积分:

Battery

我们要对黑线中的那段红线积分,积分时间是[0,t]。太阳12小时走了π,那么时刻t与这一时刻与阳光与地面的夹角θ的关系为:t=12/π*θ,所以dt=12/πdθ。下面的计算中t1对应θ1时刻,t2对应θ2时刻。

 

Battery

 

当然,之前要保证t时刻时整个区间都可以被阳光照到。

 

 #include <iostream>
 #include <cstdio>
 #include <cstring>
 #include <cmath>
 #include <algorithm>
 #define PI acos(-1.0)
 using namespace std;
 
 
 struct Node
 {
     double h,x;
 };
 
 Node a[1005],b[1005],st[1005];
 double L;
 int n,T1,T2,top;
 
 inline int DB(double x)
 {
     if(x>1e-10) return 1;
     if(x<-1e-10) return -1;
     return 0;
 }
 
 
 
 double cal1(Node a,Node b)
 {
     double k=(a.h-b.h)/(a.x-b.x);
     double x=a.x-a.h/k;
     return x;
 }
 
 
 double cal2(double x1,double x2,double h,int t)
 {
     double a=sqrt(h*h+x2*x2)-sqrt(h*h+x1*x1);
     double b=(x2-x1)*cos(PI/12.0*t);
     double c=12.0/PI;
     return c*(a-b);
 }
 
 double cal(double x1,double x2,double h,int t)
 {
     double B1,B2,B3;
     if(DB(x1)==0) B1=PI/2;
     else B1=atan(fabs(h/x1));
     B2=atan(fabs(h/x2));
     B3=PI/12*t;
     if(DB(B3-B1)>=0) return cal2(x1,x2,h,t);
     if(DB(B2-B3)>=0) return 0;
     double k=-tan(B3);
     return cal2(-h/k,x2,h,t);
 }
 
 int OK(Node a,Node b,Node c)
 {
     double k1=(a.h-b.h)/(a.x-b.x);
     double k2=(b.h-c.h)/(b.x-c.x);
     if(DB(k1-k2)==-1) return 1;
     return 0;
 }
 
 double solve(int t,Node a[])
 {
     top=0;
     st[++top]=a[1];
     double ans=0;
     int i,j;
     double x1,x2;
     for(i=2;i<=n;i++)
     {
         x1=a[i-1].x;
         x2=a[i-1].x;
         for(j=top;j>=2;j--)
         {
             x2=cal1(st[j-1],st[j]);
             if(DB(x2-a[i].x)>=0) break;
             ans+=cal(x1-st[j].x,x2-st[j].x,st[j].h,t);
             x1=x2;
         }
         ans+=cal(x1-st[j].x,a[i].x-st[j].x,st[j].h,t);
         while(top>=2&&OK(st[top-1],st[top],a[i])||top>=1&&DB(a[i].h-st[top].h)>=0)
              top--;
         st[++top]=a[i];
     }
     return ans;
 }
 
 int cmp(Node a,Node b)
 {
     return a.x<b.x;
 }
 
 double deal(int t)
 {
     double ans=0;
     int i;
     for(i=1;i<=n;i++)
     {
         b[i]=a[n+1-i];
         b[i].x=L-b[i].x;
     }
     double xx,yy,zz;
     if(t<=6) ans=solve(t,a);
     else
     {
         ans=solve(6,a);
         ans+=solve(6,b)-solve(12-t,b);
     }
     return ans;
 }
 
 int main()
 {
     while(scanf("%lf%d",&L,&n),n||L)
     {
         scanf("%d%d",&T1,&T2);
         int i;
         for(i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].h);
         sort(a+1,a+n+1,cmp);
         printf("%.5lf\n",deal(T2-6)-deal(T1-6));
     }
     return 0;
 }

 

  

 

参考:http://www.cnblogs.com/jianglangcaijin/archive/2012/10/07/2714054.html


,