Problem: moles (2017 finals)

It's dinner time! A group of **N** Foxen are standing silently in a field,
which can be represented as an infinite number line, patiently waiting for
their meals to make an appearance. The _i_th Fox is standing at position
**Pi**, with no two Foxen standing at the same position. There's also one hole
in the ground at each each integral position on the number line. Each of these
holes is the entrance to a mole's den, and the Foxen know that some of these
delicious critters are bound to show up sooner or later!

A little-known fact about Foxen is that, in addition to having an acute array
of regular senses, they possess a SONAR-like ability to emit imperceptible
sound waves and use them to discern objects at great distances. The _i_th Fox
has tuned their wavelength to a distance of **Ri**, allowing them to only
detect moles which emerge from holes at a distance of exactly **Ri** away from
them (that is, at either position **Pi** \- **Ri** or **Pi** \+ **Ri**).

All of a sudden, some number of moles have just popped up from various holes
all at once! No mole popped up at any Fox's position, no two moles popped up
from the same hole, and every mole was detected by at least one Fox.
Furthermore, each Fox _i_ has determined that there's _exactly_ 1 mole at a
distance of **Ri** away from it (as opposed to there being either 0 or 2 such
moles).

Following this initial event, there's been quite some commotion. Some moles
may have retreated back underground, and some new moles may have emerged, all
in any order. At every point in time, the set of moles on the surface is
subject to all of the same restrictions as before, with one difference: Each
Fox _i_ continues to be sure that _at least_ 1 mole is still present at a
distance of **Ri** away from it, but can no longer determine whether or not
there are perhaps now 2 such moles instead.

After some time of this, the Foxen have decided that they're ready to pounce
and "invite" some of the moles currently on the surface over for dinner.
Unfortunately, they've started to become rather overwhelmed with trying to
keep track of which moles may be on the surface, or even roughly how many of
them there might be. Assuming that the Foxen's initial observations were
correct, and that some unknown amount of time has since gone by with moles
surfacing or departing, please help the Foxen determine the number of
different quantities of moles which could possibly have ended up on the
surface.

If it's impossible for their set of initial observations to have been accurate
in the first place, output -1 instead.

### Input

Input begins with an integer **T**, the number of different fields. For each
field, there is first a line containing the integer **N**. Then **N** lines
follow, the _i_th of which contains the space-separated integers **Pi** and
**Ri**.

### Output

For the _i_th field, print a line containing "Case #**i**: " followed by a
single integer, the number of different quantities of moles which could
possibly end up on the surface at any point, or -1 if the Foxen's initial
observations must have been inaccurate.

### Constraints

1 ≤ **T** ≤ 30  
1 ≤ **N** ≤ 5,000  
0 ≤ **Pi** ≤ 1,000,000,000  
1 ≤ **Ri** ≤ 1,000,000,000  

### Explanation of Sample

In the first case, it's possible for there to eventually be 1 mole (at either
position -1 or 1), or 2 moles (at both positions -1 and 1). There can't be 0
moles due to the restriction that the Fox must detect at least 1 of them, and
there can't be more than 2 moles as they'd have to be at positions which the
Fox is unable to detect.

In the third case, it's impossible for a set of moles to have initially popped
up such that each Fox would have detected _exactly_ one of them.



Sample input:
5
1
0 1
3
4 3
8 3
11 4
6
11 5
12 5
8 1
20 4
18 3
13 4
5
25 1
22 1
26 3
13 1
19 5
17
29 1
53 5
13 8
51 6
60 2
26 3
31 26
34 24
37 8
41 11
8 37
2 8
21 7
49 39
17 12
42 2
33 19


Sample output:
Case #1: 2
Case #2: 3
Case #3: -1
Case #4: 4
Case #5: 10



Code: // Hacker Cup 2017
// Final Round
// Fox Moles
// 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-12;
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 900009

int K,A,B;
map<int,int> M;
vector<int> con[LIM],con2[LIM];
bool col0[LIM];
int col[LIM],ind[LIM],P1[LIM],P2[LIM],dist[LIM];

int Make(int i)
{
		if (M.count(i))
			return(M[i]);
	return(M[i]=K++);
}

bool DFS(int i,int c)
{
	// conflict?
		if ((col0[i]) && (c) || (col[i]>=0) && (c!=col[i]))
			return(0);
	// already coloured?
		if (col[i]>=0)
			return(1);
	// colour node and its neighbours
	col[i]=c;
	int j;
		Fox(j,Sz(con[i]))
			if (!DFS(con[i][j],1-c))
				return(0);
	return(1);
}

bool MatchBFS()
{
	int i,a,b,a2;
	queue<int> Q;
	Fill(dist,60);
		Fox(a,A)
			if (P1[a]<0)
				dist[a]=0,Q.push(a);
		while (!Q.empty())
		{
			a=Q.front(),Q.pop();
				if (dist[a]<dist[A])
					Fox(i,Sz(con2[a]))
					{
						b=con2[a][i];
						a2=P2[b];
							if (dist[a2]>=INF)
								dist[a2]=dist[a]+1,Q.push(a2);
					}
		}
	return(dist[A]<INF);
}

bool MatchDFS(int a)
{
		if (a==A)
			return(1);
	int i,b,a2;
		Fox(i,Sz(con2[a]))
		{
			b=con2[a][i];
			a2=P2[b];
				if ((dist[a2]==dist[a]+1) && (MatchDFS(a2)))
				{
					P1[a]=b;
					P2[b]=a;
					return(1);
				}
		}
	dist[a]=INF;
	return(0);
}

int MaxMatching()
{
	int a,b,m=0;
	Fill(P1,-1);
		Fox(b,B)
			P2[b]=A;
		while (MatchBFS())
		{
			Fox(a,A)
				if ((P1[a]<0) && (MatchDFS(a)))
					m++;
		}
	return(m);
}

int main()
{
	// vars
	int T,t;
	int N=0;
	int i,j,a,b,p,r,z,ans;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// init
				Fox(i,K)
					con[i].clear();
				Fox(i,A)
					con2[i].clear();
			K=0;
			M.clear();
			Fill(col0,0);
			Fill(col,-1);
			Fill(ind,-1);
			Fill(P1,-1);
			Fill(P2,-1);
			// input
			Read(N);
				while (N--)
				{
					Read(p),Read(r);
					i=Make(p),a=Make(p-r),b=Make(p+r);
					col0[i]=1;
					con[a].pb(b);
					con[b].pb(a);
				}
			// attempt to 2-color the graph (initially just from forced nodes)
				Fox(z,2)
					Fox(i,K)
						if (col[i]<0)
						{
							if ((!z) && (!col0[i]))
								continue;
							if (!DFS(i,0))
							{
								ans=-1;
								goto Done;
							}
						}
			// construct the bipartite graph, ignoring forced nodes
			A=B=0;
				Fox(i,K)
					if (!col0[i])
					{
						Fox(j,Sz(con[i]))
							if (col0[con[i][j]])
								goto Skip;
						if (!col[i])
							ind[i]=A++;
						else
							ind[i]=B++;
Skip:;
					}
				Fox(i,K)
					if ((ind[i]>=0) && (!col[i]))
					{
						a=ind[i];
							Fox(j,Sz(con[i]))
							{
								b=ind[con[i][j]];
									if (b>=0)
										con2[a].pb(b);
							}
					}
			ans=A+B-MaxMatching()+1;
			// output
Done:;
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}