Problem: poles (2017 finals)

While taking a walk through the woods, a group of Foxen have come upon a
curious sight — a row of **N** wooden poles sticking straight up out of the
ground! Who placed them there, and why? The Foxen have no clue.

Looking at the poles from the side, they can be modeled as vertical line
segments rising upwards from a number line (which represents the ground), with
the _i_th pole at distinct integral position **Pi** and having a real-valued
height of **Hi**.

One of the Foxen, Ozy, is fascinated by the shadows being cast on the ground
by the poles. The sun is shining down on the poles from some point very high
up in the sky, resulting in infinitely many rays of light descending towards
the number line at all possible positions along it, but all travelling in some
uniform direction. Each ray of light stops travelling as soon as it comes into
contact with either a pole or the ground. Any point on the ground which is
incapable of being reached by rays of light (because they would get blocked by
at least one pole before reaching that point) is considered to be covered in
shadows.

The sunlight's direction can be described by a real value _a_, with absolute
value no larger than 80, where _a_ is the signed angle difference (in degrees)
between the rays' direction and a vector pointing directly downwards. As an
example, let's imagine that there's a single pole at position 50 and with a
height of 100. If _a_ = 45, then sunlight is shining diagonally down and to
the right, meaning that the pole obstructs rays of light from being able to
reach any points on the ground in the interval [50, 150], effectively casting
a shadow with length 100 to the right. If _a_ = -45, then sunlight is shining
diagonally down and to the left, causing the pole to cast a shadow with 100 to
the left instead (over the interval [-50, 50]). If _a_ = 0, then sunlight is
shining directly downwards onto the ground, resulting in the pole not casting
any shadow.

Ozy is planning on returning by himself tomorrow in order to observe the poles
again, but he doesn't know at what time of day he'll be able to make the trip.
He does at least have it narrowed down to being within some interval of time,
during which he knows that the sunlight's direction _a_ will range from **A**
and **B**, inclusive. Given that the sunlight's direction _a_ will be a real
number drawn uniformly at random from the interval [**A**, **B**] when Ozy
visits the poles tomorrow, please help him predict the expected total length
of ground which will be covered in shadows at that time.

### Input

Input begins with an integer **T**, the number of different sets of poles. For
each set of poles, there is first a line containing the space-separated
integers **N**, **A**, and **B**. Then **N** lines follow, the _i_th of which
contains the integer **Pi** and the real number **Hi** separated by a space.
The poles' heights are given with at most 4 digits after the decimal point.

### Output

For the _i_th set of poles, print a line containing "Case #**i**: " followed
by a single real number, the expected length of ground which will be covered
in shadows. Your output should have at most 10-6 absolute or relative error.

### Constraints

1 ≤ **T** ≤ 30  
1 ≤ **N** ≤ 500,000  
-80 ≤ **A** < **B** ≤ 80   
0 ≤ **Pi** ≤ 1,000,000,000  
1 ≤ **Hi** ≤ 1,000,000  
The sum of **N** values across all **T** cases does not exceed 2,000,000.

### Explanation of Sample

In the first case, the sunlight's direction _a_ is drawn uniformly at random
from the interval [44, 46]. As described above, the length of ground covered
in shadows when _a_ = 45 is exactly 100. When _a_ = 44, the shadow's length is
~96.57, and when _a_ = 46, its length is ~103.55. However, note that its
expected length for this distribution of possible _a_ values is not equal to
the average of those sample lengths.



Sample input:
5
1 44 46
50 100.0
2 44 46
50 100.0
150 100.0
3 -80 74
0 4.2
1 1.0
2 2.3
5 -55 0
5555 555.55
5055 505.0005
5550 500.5
50005 50550.505
5505 55.05
14 -71 58
185 32.6
128 54.3
169 52.8
125 8.2
144 41.9
166 61.5
131 100.4
94 43.2
172 93.2
120 131.6
149 11.0
158 7.1
181 39.6
145 41.9


Sample output:
Case #1: 100.020314016
Case #2: 199.157629122
Case #3: 5.731972014
Case #4: 29594.141688738
Case #5: 155.088749996



Code: // Hacker Cup 2017
// Final Round
// Fox Poles
// Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }

const int INF = (int)1e9;
const LD EPS = 1e-10;
const LD PI = acos(-1.0);

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=getchar();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 800001

pair<int,LD> O[LIM],P[LIM];
LD mx[LIM];
vector<int> ch[LIM];
int ss,st[LIM];

LD Calc(LD h,LD a1,LD a2)
{
	return(-h*(log(cos(a2))-log(cos(a1))));
}

int main()
{
	// vars
	int T,t;
	int N;
	bool D[2];
	LD A[2];
	int i,j,c,p,w,z;
	double v;
	LD a,a1,a2,tot,ans[2];
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(N);
				Fox(i,2)
				{
					Read(j);
					D[i]=int(j<0);
					A[i]=j*PI/180;
				}
				Fox(i,N)
				{
					scanf("%d%lf",&O[i].x,&v);
					O[i].y=v;
				}
			// consider each direction
				Fox(z,2)
				{
					// reverse poles horizontally if necessary
					memcpy(P,O,sizeof(P));
						if (D[z])
							Fox(i,N)
								P[i].x=-P[i].x;
					// sort poles left-to-right
					sort(P,P+N);
					// init
						Fox(i,N+1)
							ch[i].clear();
					// consider poles left-to-right, constructing convex hull of coverage
					ss=0;
						Fox(i,N)
						{
							// find this pole's parent, if any
								while (ss>0)
								{
									j=st[ss-1];
									a=atan2(P[i].x-P[j].x,P[j].y-P[i].y);
										if (a<mx[j]-EPS)
											break;
									ss--;
								}
								if (!ss)
								{
									mx[i]=Abs(A[z]);
									ch[N].pb(i);
								}
								else
								{
									mx[i]=a;
									ch[j].pb(i);
								}
							st[ss++]=i;
						}
					// augment tree
						Fox(j,Sz(ch[N])-1)
							ch[ch[N][j]].pb(ch[N][j+1]);
						Fox(i,N)
							Fox(j,Sz(ch[i])-1)
								ch[ch[i][j]].pb(ch[i][j+1]);
					// consider each left pole
					ans[z]=0;
						Fox(i,N)
						{
							a=0;
								Fox(c,Sz(ch[i]))
								{
									j=ch[i][c];
									a1=max(a,atan2(P[j].x-P[i].x,P[i].y));
									a2=atan2(P[j].x-P[i].x,P[i].y-P[j].y);
									// partial shadow until bottom
										if (a1>mx[i]-EPS)
											break;
									ans[z]+=Calc(P[i].y,a,a1);
									// full shadow until top
									w=P[j].x-P[i].x;
										if (a2>mx[i]-EPS)
										{
											ans[z]+=w*(mx[i]-a1);
											goto Done;
										}
									ans[z]+=w*(a2-a1);
									a=a2;
								}
							ans[z]+=Calc(P[i].y,a,mx[i]);
Done:;
						}
				}
			// compute answer
				if (D[0]==D[1])
					tot=Abs(ans[0]-ans[1]);
				else
					tot=ans[0]+ans[1];
			tot/=A[1]-A[0];
			// output
			printf("Case #%d: %.9lf\n",t,(double)tot);
		}
	return(0);
}