#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <cmath>
#include <ctime>

using namespace std;

// Třída pro logování výpočtů
class Logovani {
	ofstream ofs;
public:
	void open(int x) {
		stringstream name;
		name << "beh" << x << ".log";
		ofs.open(name.str().c_str());
	}
	void close() {
		ofs.close();
	}
	void write(vector<double> fitness, int it) {
		double mini = 99999999;
		double total = 0;
		for (int i=0; i<fitness.size(); i++) {
			total += fitness[i];
			mini = min(mini, fitness[i]);
		}
		ofs << it << "\t" << total/fitness.size() << "\t" << mini << endl;
	}
} LOG;

/* Náhodné číslo z intervalu [0, 1) */
double randdouble() {
    return rand()/(double(RAND_MAX)+1);
}

void randperm(vector<int> &p) {
	int n = p.size();
	for (int i=1; i<n; i++) {
		swap(p[i], p[rand()%(i+1)]);
	}
}

/* Parametry algoritmu */
int N0 = 100;		// Velikost populace
int N;
int D;			// Velikost jedince
double F = 0.5;		// Koeficient mutace
double C = 0.3;		// Pravděpodobnost křížení
int IT = 1500;		// Maximální počet iterací
int BEHY = 3;		// Počet běhů celého algoritmu

double MIN_X = -3.0;	// Minimální možná hodnota jedné složky jedince
double MAX_X = 15.0;	// Maximální možná hodnota jedné složky jedince
// Populace a její fitness
vector<vector<double> > populace;
vector<double> fitness;
// Dárci
vector<vector<double> > darci;
// Noví jedinci a jejich fitness
vector<vector<double> > novi;
vector<double> novi_fitness;
// Nejlepší jedinec a jeho fitness
vector<double> best;
double best_fitness;
// Fitness nejlepšího zalogovaného
double best_log = 999999999;

double W, H; int K;
vector<double> w;
vector<double> h;

/* Ohodnocující funkce jedince */
/* Momentálně nastavená pro vývoj jedince, kde v[i] = i
 * Změňte v závislosti na vámi řešeném problému
 */
double ohodnot_jedince(vector<double> v) {
	double res = 0;
	for (int i=0; i<K; i++) {
		double x1,y1,x2,y2;
		x1 = max(v[2*i], 0.0);
		y1 = max(v[2*i+1], 0.0);
		x2 = min(v[2*i]+w[i], W);
		y2 = min(v[2*i+1]+h[i], H);
		res += w[i]*h[i] - ((x1<x2 && y1<y2) ? ((x2-x1)*(y2-y1)) : 0);
	}
	for (int i=0; i<K; i++) {
		for (int j=i+1; j<K; j++) {
			double x1,x2,y1,y2;
			x1 = max(v[2*i], v[2*j]);
			y1 = max(v[2*i+1], v[2*j+1]);
			x2 = min(v[2*i]+w[i], v[2*j]+w[j]);
			y2 = min(v[2*i+1]+h[i], v[2*j+1]+h[j]);
			res += (x1<x2 && y1<y2) ? ((x2-x1)*(y2-y1)) : 0;
		}
	}
	return res;
}

/* Vygeneruje náhodného jedince délky d s hodnotami mezi MIN_X a MAX_X */
vector<double> generuj_jedince(int k) {
	vector<double> v(2*k);
	for (int i=0; i<k; i++) {
		v[2*i] = randdouble()*(W - w[i]);
		v[2*i+1] = randdouble()*(H - h[i]);
	}
	return v;
}

/* Inicializuje počáteční populaci */
void init_populace() {
	// Vygeneruj nové jedince
	populace.clear();
	for (int i=0; i<N0; i++) {
		populace.push_back(generuj_jedince(K));
	}
	// Přečte ze souboru předgenerované jedince a přidá do populace
	ifstream ifs("jedinci.txt");
	int N1;
	ifs >> N1;
	for (int i=0; i<N1; i++) {
		vector<double> v(D);
		for (int j=0; j<D; j++) {
			ifs >> v[j];
		}
		populace.push_back(v);
	}
	ifs.close();
	N = N0 + N1;
	// Spočítej jejich fitness
	fitness.clear();
	fitness = vector<double>(N);
	best_fitness = 9999999; int index = -1;
	for (int i=0; i<N; i++) {
		fitness[i] = ohodnot_jedince(populace[i]);
		if (fitness[i] < best_fitness) {
			best_fitness = fitness[i];
			index = i;
		}
	}
	// Zkopiruj si nejlepšího
	best = vector<double>(D);
	for (int i=0; i<D; i++) best[i] = populace[index][i];
}

/* Ze tří zadaných jedinců vytvoří dárce */
vector<double> vytvor_darce(vector<double> &p, vector<double> &q, vector<double> &r) {
	vector<double> d(D);
	for (int i=0; i<D; i++) {
		d[i] = p[i] + F*(q[i]-r[i]);
	}
	return d;
}

/* Provede křížení dárce a původního jedince */
vector<double> krizeni(vector<double> &x, vector<double> &d) {
	vector<double> y(D);
	int j = rand()%K;	// Náhodný gen, který se určitě vezme z dárce
	double pst = randdouble();
	for (int i=0; i<K; i++) {
		if (pst < C || i==j) {
			y[2*i] = d[2*i];
			y[2*i+1] = d[2*i+1];
		}
		else {
			y[2*i] = x[2*i];
			y[2*i+1] = x[2*i+1];
		}
	}
	return y;
}

/* Průběh celého algoritmu */
void diferencialni_evoluce() {
	init_populace();
	// Inicializace tří permutací
	vector<int> p(N);
	vector<int> q(N);
	vector<int> r(N);
	for (int i=0; i<N; i++) p[i] = q[i] = r[i] = i;
	for (int it=0; it < IT; it++) {
		if (it%10==0) {
			LOG.write(fitness, it);
		}
		darci.clear();
		// Generování náhodných permutací
		randperm(p);
		randperm(q);
		randperm(r);
		// Vytvoření dárců (mutace)
		for (int i=0; i<N; i++) {
			darci.push_back(vytvor_darce(populace[p[i]], populace[q[i]], populace[r[i]]));
		}
		// Křížení
		novi.clear();
		novi_fitness.clear();
		for (int i=0; i<N; i++) {
			vector<double> y = krizeni(populace[i], darci[i]);
			novi.push_back(y);
			novi_fitness.push_back(ohodnot_jedince(y));
		}
		// Selekce -- vybere lepšího z původního a nového jedince
		int index = -1;
		for (int i=0; i<N; i++) {
			if (novi_fitness[i] <= fitness[i]) {
				swap(populace[i], novi[i]);
				swap(fitness[i], novi_fitness[i]);
			}
			// Pamatuj si index nejlepšího jedince
			if (fitness[i] < best_fitness) {
				index = i;
				best_fitness = fitness[i];
			}
		}
		// Pokud jsme našli nejlepšího, zapamatujeme si jej
		if (index!=-1) {
			for (int i=0; i<D; i++) best[i] = populace[index][i];
		}
	}
	LOG.write(fitness, IT);
}

/* Zapíše do souboru fitness a geny nejlepšího jedince */
void zaloguj_nejlepsiho(vector<double> best) {
	ofstream ofs("best.log");
	ofs << "Fitness: " << best_fitness << endl;
	ofs << "Geny:" << endl;
	for (int i=0; i<best.size(); i++)
		ofs << best[i] << " ";
	ofs << endl;
	best_log = best_fitness;
}

int main() {
	// Nacteni dat
	cin >> W >> H;
	cin >> K;
	D = 2*K;
	for (int i=0; i<K; i++) {
		int wi, he; cin >> wi >> he;
		w.push_back(wi); h.push_back(he);
	}
	srand(time(NULL));	// Zadejte své datum narození jako DDMMYYYY
	// Spusť několik nezávislých běhů
	for (int b=0; b<BEHY; b++) {
		cout << "Beh " << b << endl;
		LOG.open(b);
		diferencialni_evoluce();
		LOG.close();
		// Pokud máme nového nejlepšího jedince, zalogujeme jej
		if (best_log > best_fitness) {
			zaloguj_nejlepsiho(best);
		}
	}
	return 0;
}