2015
05-24

# 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.

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

（1）

（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）然后就是对于每一段的发电量就是一个积分：

 #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;
}


,