Problem: bigtop (2017 round2)

Come one, come all! The most famous circus troupe in all the land is on tour!
Having just arrived in a new location, they're eager to set up their big top
and showcase world-class acts of acrobatics and comedy for their audience.

Looking at the tent from the side (as a cross section), it will be set up
along a one-dimensional strip of ground. **N** vertical poles will be placed
in the ground, one after another, with the _i_th pole at a position **Xi**
meters to the right of an arbitrary reference point, and reaching a height of
**Hi** meters. No two poles will be at the same position.

After each pole is placed, the shape of the tent will be updated to fit the
current set of poles. In particular, the upper outline of the tent will be a
function with the following properties:

  1. it's defined over all positions from negative infinity to positive infinity 
  2. its height is always non-negative 
  3. it's made up entirely of a series of connected line segments, with each one having a slope with absolute value no greater than 1 (meaning that the function is continuous, and its height may never change from left to right at an angle of more than 45 degrees up/down) 
  4. it doesn't intersect with any of the poles (meaning that, at each pole's position, the function's height must be no smaller than that of the pole) 

The cross-sectional area of the tent is the area under this function. Despite
their popularity, the circus troupe doesn't exactly have money to spare on
tent materials (with most of their budget allocated to feeding their flying
elephant star). As such, they'd like to minimize the cross-sectional area of
their tent after placing each of the **N** poles. They'd like you to calculate
the sum of these **N** minimal areas for them.

In this example, three poles are placed one after another. The first is at X =
20 with height 10. The minimum area of the tent is 100 m2. The second pole is
placed at X = 30 with a height of 15. The minimum area of the tent is now
268.75 m2. The third pole is at X = 24 with a height of 3. This doesn't change
the minimum area of the tent, which is still 268.75 m2.

![]({{PHOTO_ID:1437352136460846}}) ![]({{PHOTO_ID:1162015730825186}})
![]({{PHOTO_ID:262229418531119}})

You're given **X1**, and **X2..N** may then be calculated as follows, using
given constants **Ax**, **Bx**, and **Cx** (note that it is guaranteed that
**X1..N** will be distinct):

**Xi** = ((**Ax** * **Xi-1** \+ **Bx**) % **Cx**) + 1 

Similarly, you're given **H1**, and **H2..N** may then be calculated as
follows, using given constants **Ah**, **Bh**, and **Ch**:

**Hi** = ((**Ah** * **Hi-1** \+ **Bh**) % **Ch**) + 1 

### Input

Input begins with an integer **T**, the number of different tents that the
circus troupe will set up. For each tent, there is first a line containing the
single integer **N**. Then there is a line containing the four space-separated
integers **X1**, **Ax**, **Bx**, and **Cx**. Then there is a line containing
the four space-separated integers **H1**, **Ah**, **Bh**, and **Ch**.

### Output

For the _i_th tent, print a line containing "Case #**i**: " followed by one
real number. This number is the sum of **N** values, the _j_th of which is the
minimum possible cross-sectional area of the tent after poles 1 through _j_
have been placed.

Answers that have a relative error of up to 10-6 will be accepted as correct.

### Constraints

1 ≤ **T** ≤ 150  
1 ≤ **N** ≤ 800,000  
1 ≤ **X1** ≤ 10,000,000  
0 ≤ **Ax**, **Bx** ≤ 10,000,000  
1 ≤ **Cx** ≤ 10,000,000  
1 ≤ **H1** ≤ 100,000  
0 ≤ **Ah**, **Bh** ≤ 100,000  
1 ≤ **Ch** ≤ 100,000  

### Explanation of Sample

In the first case, the cross-sectional areas of the tent after each pole is
erected are 1.0, 1.75, 2.5, 3.25, and 4.0 for a total of 12.50.



Sample input:
5
5
1 1 0 100
1 0 0 100
5
1 1 0 100
1 1 0 100
10
1 1 1 100
1 0 0 100
13
3 3 0 100
7 7 0 100
800
1 13107 5 12917
1 12917 5 13107


Sample output:
Case #1: 12.50
Case #2: 55.0
Case #3: 55.0
Case #4: 74630.0
Case #5: 256744091587.25



Code: // Hacker Cup 2017
// Round 2
// Big Top
// 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-9;
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);
}

LL ans;
set<PR> S;

LL Area(PR a,PR b)
{
	LD o=max((LD)0,(LD)a.y+b.y-((LD)b.x-a.x));
	return((LL)a.y*a.y*2 + (LL)b.y*b.y*2 - o*o);
}

void Add(PR p)
{
	set<PR>::iterator I,J;
	S.insert(p);
	I=J=S.find(p),I--,J++;
	ans-=Area(*I,*J);
	ans+=Area(*I,p)+Area(p,*J);
}

void Del(set<PR>::iterator J)
{
	set<PR>::iterator I,K;
	I=K=J,I--,K++;
	ans-=Area(*I,*J)+Area(*J,*K);
	ans+=Area(*I,*K);
	S.erase(J);
}

int main()
{
	int T,t;
	int N;
	int X,Ax,Bx,Cx;
	int H,Ah,Bh,Ch;
	PR p;
	LL tot;
	set<PR>::iterator I,J,K;
	Read(T);
		Fox1(t,T)
		{
			S.clear();
			S.insert(mp(-INF-5,0));
			S.insert(mp(INF*2+5,0));
			ans=tot=0;
			Read(N);
			Read(X),Read(Ax),Read(Bx),Read(Cx);
			Read(H),Read(Ah),Read(Bh),Read(Ch);
				while (N--)
				{
					p=mp(X,H);
					I=J=S.lower_bound(p),I--;
						if (p.y<=(I->y)-(p.x-(I->x)))
							goto Skip;
						if (p.y<=(J->y)-((J->x)-p.x))
							goto Skip;
						while ((I->y)<=p.y-(p.x-(I->x)))
						{
							K=I,I--;
							Del(K);
						}
						while ((J->y)<=p.y-((J->x)-p.x))
						{
							K=J,J++;
							Del(K);
						}
					Add(p);
Skip:;
					tot+=ans;
					X=((LL)Ax*X+Bx)%Cx+1;
					H=((LL)Ah*H+Bh)%Ch+1;
				}
			printf("Case #%d: %lld.%lld\n",t,tot/4,(tot%4)*25);
		}
	return(0);
}