// RoadConstruction.cpp : Defines the entry point for the console application.

//

// by Adrian Dale 15/12/2008

// Solution to the IEEE Challenge 2008 - Road Construction

// http://www.ieee.org/portal/cms_docs_iportals/iportals/membership/students/scholarshipsawardscontests/IEEEXtreme2008_Competition_Booklet.pdf

//

// This code works by first parsing the input data into a minimal set of constraints

// needed to solve the problem. That is, we only need to take into account the houses

// that are closest to each side of the road. So, for each row we store the widest allowed

// distance from the road to the left of the road and to the right of the road.

//

// We then use a recursive function to try out all possible starting positions of

// each parcel of land to see what area of land they give.

// We record the maximum area once all possible parcel subdivisions have been tested

// and output it as the puzzle answer.

#include "stdafx.h"

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

// Data structures to hold the road map data

// We don't need to hold a 2D array, since some of the house data is likely

// to be redundant.

// All we need to know for each row is the smallest possible rectangle we

// could fit on that row

struct BoardRow

{

int Left;

int Right;

};

vector<BoardRow> Board;

typedef vector<BoardRow>::iterator BoardIter;

// We get given this number - the number of parcels of land we must divide the

// map into

int Parcels = 0;

// We get given this number - Height is how long the road is

int Height = 0;

int Width = 0;

// We need this to store the maximum area so far as we go through our recursive

// algorithm.

int MaxParcelArea = 0;

// ReadInput reads the challenge parameters from stdin.

// See challenge for input format.

// Note that this function assumes the input data is valid.

// Not a great assumption but should do for this quick and dirty code.

void ReadInput()

{

int Houses = 0;

// Height of the board comes first in the input

cin >> Height;

// We'll have a row for each square of height

Board.resize(Height);

// Next input value is width

cin >> Width;

// Width of map marks the min and max possible widths of a rectangle

// at each y coordinate. Note that a Width of n is equivalent to a house at n+1

// Adding in the houses will narrow these constraints

for( BoardIter it=Board.begin(); it != Board.end(); ++it )

{

it->Left = -1 * (Width+1);

it->Right = Width+1;

}

// Read in count of number of parcels of land

cin >> Parcels;

// Read in the number of houses - we use this to tell us how many

// sets of input coordinates to expect

cin >> Houses;

for( int i=0; i<Houses; ++i )

{

int HouseX = 0;

int HouseY = 0;

cin >> HouseY;

cin >> HouseX;

// Decrement HouseY so we can use it as an array index.

// For some reason the rows seem to

// be numbered from 1 in the input.

--HouseY;

if ( HouseX < 0 )

{

// Only update the board with the house coordinates if it narrows the

// constraints

if ( HouseX > Board[HouseY].Left)

Board[HouseY].Left = HouseX;

}

else

{

if ( HouseX < Board[HouseY].Right)

Board[HouseY].Right = HouseX;

}

}

}

// GetParcelArea returns the area covered by the passed in

// allocation of the parcels

int GetParcelArea( vector<int> &ParcelList )

{

int TotalParcelArea = 0;

// Parcel list comes in as a vector of starting positions

// for each parcel, numbered from 0.

// Go through each parcel in the list and add its area to the

// TotalParcelArea

for ( int parcelNo=0; parcelNo<ParcelList.size(); ++parcelNo )

{

// We're given the start row of each parcel.

// The end row is the one before the start of the next parcel,

// or the top of the map for the last parcel

int ParcelStart = ParcelList[parcelNo];

int ParcelEnd;

if ( parcelNo < ParcelList.size() - 1 )

ParcelEnd = ParcelList[parcelNo+1];

else

ParcelEnd = Height;

// Work out the widest rectancle we can fit in this parcel's

// range of rows by looping through the constraints for each

// row that makes up the parcel

int MaxLeft = -1*(Width+1);

int MinRight = Width+1;

for( int i=ParcelStart; i<ParcelEnd; ++i )

{

if ( Board[i].Left > MaxLeft)

MaxLeft = Board[i].Left;

if ( Board[i].Right < MinRight)

MinRight = Board[i].Right;

}

// Very simple formula for area of a rectangle!

int ParcelArea = (MinRight - MaxLeft - 1) * (ParcelEnd - ParcelStart);

TotalParcelArea += ParcelArea;

}

return TotalParcelArea;

}

// This function recursively tries all possible parcel

// sizes into the parcel list

void TryParcelList( vector<int> ParcelList, int parcelNo )

{

if ( parcelNo == Parcels )

{

// We've filled our list of guesses, so try it out

int GuessArea = GetParcelArea( ParcelList );

if ( GuessArea > MaxParcelArea )

MaxParcelArea = GuessArea;

}

else

{

// Still some more parcels to allocate, so call this fn recursively

// for each possible parcel left at this level, starting from

// where the previous ones left off, and finishing with enough room for

// all remaining parcels of minimum size

for (int i=ParcelList[parcelNo-1] + 1; i <= Height - Parcels + parcelNo; ++i )

{

ParcelList[parcelNo] = i;

TryParcelList( ParcelList, parcelNo + 1 );

}

}

}

// This function kicks off the recursive search for the best possible subdivision

// of the map into parcels.

int GetMaxParcelArea()

{

vector<int> ParcelList;

ParcelList.resize(Parcels);

MaxParcelArea = 0;

// First piece always starts at zero

ParcelList[0] = 0;

// Kick off the recursive function

TryParcelList( ParcelList, 1 );

return MaxParcelArea;

}

int _tmain(int argc, _TCHAR* argv[])

{

ReadInput();

cout << GetMaxParcelArea() << endl;

return 0;

}