{
  CTU Open Contest 2002
  =====================
  Sample solution for the problem: holes

  Martin Kacer, Oct 2002
}

Program Holes;

Const MAXCUT = 128;   {must be at least one cut bigger than stated}
	MAXCOORD = (MAXCUT*2);
	MAXFIELD = (MAXCOORD*2);

Type
	TCutX = Record X1, X2: Integer; Y: Integer; End;
	TCutY = Record X: Integer; Y1, Y2: Integer; End;
	TConv = Array [1..MAXCOORD] of Integer;

Var CutX : Array [1..MAXCUT] of TCutX;
	CutY : Array [1..MAXCUT] of TCutY;
	NumCutX, NumCutY : Integer;
	ConvTblX, ConvTblY : TConv;
	NumConvX, NumConvY : Integer;
	Field : Array [0..MAXFIELD,0..MAXFIELD] of Boolean;
	MaxFldX, MaxFldY : Integer;
	QX, QY : Array [1..MAXFIELD*MAXFIELD] of Integer;
	QB, QE : Integer;


Procedure DbgPrint;
Var I, J: Integer;
Begin
	For J := 1 to MaxFldY do
	Begin
		For I := 1 to MaxFldX do
			If Field[I,J] then
				Write ('#')
			else
				Write ('.');
		WriteLn;
	End;
End; { DbgPrint }

Procedure DbgCuts;
Var I: Integer;
Begin
	For I := 1 to NumCutX do
		WriteLn ('X', I, ': ', CutX[I].X1, ' ', CutX[I].X2, ' ', CutX[I].Y);
	For I := 1 to NumCutY do
		WriteLn ('Y', I, ': ', CutY[I].X, ' ', CutY[I].Y1, ' ', CutY[I].Y2);
End; { DbgCuts }


{sort and uniq both horizontal and vertical coordinates}
Procedure SortCoordinates (Var Tbl: TConv; Var N: Integer);
Var I, J: Integer;
	X: Integer;
Begin
	If (N > 1) then For I := N-1 downto 1 do
		For J := 1 to I do
			If (Tbl[J] > Tbl[J+1]) then
			Begin
				X := Tbl[J]; Tbl[J] := Tbl[J+1]; Tbl[J+1] := X;
			End;
	I := 2;
	J := 2;
	While (J <= N) do
	Begin
		While (J <= N) and (Tbl[J-1] = Tbl[J]) do Inc (J);
		if (J <= N) then
		Begin
			Tbl[I] := Tbl[J];
			Inc (I);
			Inc (J);
		End;
	End;
	N := I - 1;
End; { SortCuts }


{read cut descriptions}
Procedure ReadCuts (N: Integer);
Var I: Integer;
	X1, Y1, X2, Y2: Integer;
Begin
	NumCutX := 0; NumCutY := 0;
	NumConvX := 0; NumConvY := 0;
	For I := 1 to N do
	Begin
		ReadLn (X1, Y1, X2, Y2);
		If (X1 = X2) then
		Begin
			Inc (NumCutY);
			CutY[NumCutY].X := X1;
			if (Y1 < Y2) then Begin
				CutY[NumCutY].Y1 := Y1;
				CutY[NumCutY].Y2 := Y2;
			End else Begin
				CutY[NumCutY].Y1 := Y2;
				CutY[NumCutY].Y2 := Y1;
			End;
			Inc (NumConvX); ConvTblX[NumConvX] := X1;
			Inc (NumConvY); ConvTblY[NumConvY] := Y1;
			Inc (NumConvY); ConvTblY[NumConvY] := Y2;
		End else Begin
			Inc (NumCutX);
			CutX[NumCutX].Y := Y1;
			if (X1 < X2) then Begin
				CutX[NumCutX].X1 := X1;
				CutX[NumCutX].X2 := X2;
			End else Begin
				CutX[NumCutX].X1 := X2;
				CutX[NumCutX].X2 := X1;
			End;
			Inc (NumConvX); ConvTblX[NumConvX] := X1;
			Inc (NumConvX); ConvTblX[NumConvX] := X2;
			Inc (NumConvY); ConvTblY[NumConvY] := Y1;
		End;
	End;
	SortCoordinates (ConvTblX, NumConvX);
	SortCoordinates (ConvTblY, NumConvY);
End; { ReadCuts }


{convert an original coordinate to a smaller one;
return the position of the coordinate in the sorted and uniq array}
Function ConvertX (X: Integer) : Integer;
Var I, R: Integer;
Begin
	R := 0;
	For I := 1 to NumConvX do
		If (X = ConvTblX[I]) and (R = 0) then R := I;
	ConvertX := R;
End; { ConvertX }

Function ConvertY (Y: Integer) : Integer;
Var I, R: Integer;
Begin
	R := 0;
	For I := 1 to NumConvY do
		If (Y = ConvTblY[I]) and (R = 0) then R := I;
	ConvertY := R;
End; { ConvertY }


{convert all coordinates to the small ones}
Procedure ConvertCuts;
Var I: Integer;
Begin
	For I := 1 to NumCutX do
	Begin
		CutX[I].Y := ConvertY (CutX[I].Y);
		CutX[I].X1 := ConvertX (CutX[I].X1);
		CutX[I].X2 := ConvertX (CutX[I].X2);
	End;
	For I := 1 to NumCutY do
	Begin
		CutY[I].Y1 := ConvertY (CutY[I].Y1);
		CutY[I].Y2 := ConvertY (CutY[I].Y2);
		CutY[I].X := ConvertX (CutY[I].X);
	End;
End;


{clear the whole field}
Procedure PrepareField;
Var X, Y: Integer;
Begin
	For X := 1 to MAXFIELD do
		For Y := 1 to MAXFIELD do
			Field[X, Y] := false;
	MaxFldX := NumConvX * 2 + 2;
	MaxFldY := NumConvY * 2 + 2;
End; { PrepareField }


{draw lines representing cuts to the field;
drawing is done either with True of False (erasing);
only lines leading through an empty area are drawn - this makes
no difference when drawing but is important when erasing}
Procedure DrawCuts (Color: Boolean);
Var X, Y: Integer;
	I: Integer;
Begin
	For I := 1 to NumCutX do
		For X := 2*CutX[I].X1 to 2*CutX[I].X2 do
			If not Field[X, 2*CutX[I].Y-1]
					and not Field[X, 2*CutX[I].Y+1] then
				Field[X, 2*CutX[I].Y] := Color;
	For I := 1 to NumCutY do
		For Y := 2*CutY[I].Y1 to 2*CutY[I].Y2 do
			If not Field[2*CutY[I].X+1, Y]
					and not Field[2*CutY[I].X-1, Y] then
				Field[2*CutY[I].X, Y] := Color;
End; { DrawCuts }


{enqueue the given point if it is free}
Procedure Enqueue (X, Y: Integer);
Begin
	If not Field[X,Y] then
	Begin
		Field[X,Y] := true;
		QX[QE] := X; QY[QE] := Y;
		Inc (QE);
	End;
End;


{seed-fill the given area}
Procedure SeedFill (X, Y: Integer);
Begin
	QB := 1; QE := 1;
	Enqueue (X, Y);
	While (QB < QE) do
	Begin
		X := QX[QB]; Y := QY[QB];
		Inc (QB);
		If (X > 1) then Enqueue (X-1, Y);
		If (X <= MaxFldX) then Enqueue (X+1, Y);
		If (Y > 1) then Enqueue (X, Y-1);
		If (Y <= MaxFldY) then Enqueue (X, Y+1);
	End;
End; { SeedFill }


{count all the holes in the given situation}
Function CountHoles : Integer;
Var X, Y: Integer;
	Cnt: Integer;
Begin
	Cnt := 0;
	For X := 1 to MaxFldX do
		For Y := 1 to MaxFldY do
			If not Field[X,Y] then
			Begin
				SeedFill (X, Y);
				Inc (Cnt);
			End;
	CountHoles := Cnt;
End; { CountHoles }


{solve one situation}
Function SolveOne (N: Integer): Integer;
Begin
	ReadCuts (N);
	ConvertCuts;
	PrepareField;
	DrawCuts (true);
	SeedFill (1, 1);
	DrawCuts (false);
	SolveOne := CountHoles;
End;


Var N: Integer;

Begin
	Repeat
		ReadLn (N);
		If (N > 0) then
			WriteLn ('There are ',SolveOne (N),' holes.');
	until (N = 0);
End.

