Информатика и математика

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.



acm.pku 1255 Floors

Сообщений 1 страница 3 из 3

1

http://acm.pku.edu.cn/JudgeOnline/problem?id=1255

   Задача: Полы
   С целью уменьшения пробок между пунктами A и B решено было построить новое шоссе. Его строительству препятствовал старый особняк, который было решено снести.
   Перед сносом выяснилось, что красочные плиточные полы в особняке сделаны знаменитым художником Мондриани и поэтому они имеют большую историческую и культурную ценность и должны быть сохранены. Естественно, что полы должны быть удалены из здания до того, как особняк будет снесен.
   Для выполнения этих работ был приглашен эксперт, который решил для облегчения перемещения пола разрезать его на более мелкие прямоугольные части, причем делать разрез он мог только на соединении плиток параллельно одной из сторон по всему полу. Например, пол, изображенный на рис. 1, может быть легко разделен на 9 частей; пол, изображенный на рис. 2 вообще не может быть разрезан, а пол, изображенный на рис. 3 может быть разделен на 6 частей.

http://acm.pku.edu.cn/JudgeOnline/images/1255_1.jpg

   При подготовке к работе по перемещению пола, эксперт должен знать, насколько тяжелыми будут образованные после разреза части. Так как пол имеет одинаковую толщину и изготовлен из одного и того же материала,  вес каждой части зависит только от размеров образованных прямоугольников.
   Найдите для каждого тестового случая площадь наибольшей части пола после разрезания. Делать разрезы по плитке запрещено. Разрез можно делать только по всей ширине или высоте исходной части вдоль стыка и параллельно одной из исходных сторон.

   Технические условия: Первым числом во входных данных является количество тестовых случаев.  Для каждого тестового случая первая строка задает размеры пола: длину и ширину. Следующая строка задает количество плиток в полу t (1 <= t <= 100). Следующие t строк каждого тестового случая дают описание каждой плитки: xl yl xh yh, где (xl, yl) - координаты левого нижнего угла плитки, а (xh, yh) - координаты ее правого верхнего угла. Плитки взаимно не перекрываются и покрывают весь пол.  Все данные - неотрицательные целые числа.
   Выходные данные содержат для каждого тестового случая в новой строке найденное значение наибольшей площади.

   Пример входных данных:

2
300 400
3
0 0 300 200
0 200 200 400
200 200 300 400
300 300
5
0 0 200 100
200 0 300 200
0 100 100 300
100 200 300 300
100 100 200 200

   Пример выходных данных:

60000
90000

   Анализ условия и разбор решения:

Код:
/* GNU C */
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#define MAXSIZE(40000)
#define MAXTILES	(100)
int flength, fwidth;
int ntiles;
int tilexl[MAXTILES], tilexh[MAXTILES];
int tileyl[MAXTILES], tileyh[MAXTILES];
int tilearea[MAXTILES];
int npieces;
int tiles_by_piece[MAXTILES];	/* Tile nrs grouped by piece */
int piece_offset[MAXTILES];	/* Offset into tile_xx_sorted arrays */
int piece_ntiles[MAXTILES];	/* Nr of tiles in this piece */
int piece_area[MAXTILES];	/* Area of this piece */

/* Solution */
int best_area;


/*
 *  Read description of a floor
 */
void read_input()
{
	int i;

	scanf("%d %d\n", &flength, &fwidth);
	assert(flength > 0 && flength <= MAXSIZE);
	assert(fwidth > 0  && fwidth <= MAXSIZE);

	scanf("%d\n", &ntiles);
	assert(ntiles >= 1 && ntiles <= MAXTILES);

	for (i = 0; i < ntiles; i++) {
int xl, xh, yl, yh;
scanf("%d %d %d %d\n", &xl, &yl, &xh, &yh);
assert(xl >= 0 && xl < xh && xh <= flength);
assert(yl >= 0 && yl < yh && yh <= fwidth);
tilexl[i] = xl;  tilexh[i] = xh;
tileyl[i] = yl;  tileyh[i] = yh;
tilearea[i] = (xh - xl) * (yh - yl);
	}
}
static void fix_piece_area(int piece)
{
	int offs = piece_offset[piece];
	int n = piece_ntiles[piece];
	int area = 0;
	int i;
	for (i = 0; i < n; i++)
area += tilearea[tiles_by_piece[offs+i]];
	piece_area[piece] = area;
}


/* Helper function for qsort-ing integers */
static int compare_int(const void *ap, const void *bp)
{
	int a = *(int*)ap, b = *(int*)bp;
	return (a < b) ? -1 : (a > b) ? 1 : 0;
}

/*
 *  Cut this piece if possible. If (fixy) then try to cut along a
 *  fixed-Y line, else try to cut along a fixed-X line.
 *  Return 1 if the cut was successful.
 */
static int try_cut_piece_1d(int piece, int fixy)
{
	int offs = piece_offset[piece];
	int n = piece_ntiles[piece];
	const int *tilelow, *tilehigh;
	int lbounds[MAXTILES], hbounds[MAXTILES];
	int n_intervals, cut, newoffs, newpiece;
	int i, j;

	/*
	 * tilelow[] and tilehigh[] are the lower and upper coordinates
	 * of the tiles for the dimension we are considering.
	 */
	tilelow =  (fixy) ? tileyl : tilexl;
	tilehigh = (fixy) ? tileyh : tilexh;
	
	/*
	 * Find the set of 1D-intervals of all tiles in the specified piece.
	 * Eliminate empty intervals (they don't block any cuts anyway).
	 * Produce a sorted list of the lower bounds and upper bounds of
	 * the resulting intervals.
	 */

	n_intervals = 0;
	for (i = 0; i < n; i++) {
int tile, low, high;
tile = tiles_by_piece[offs+i];
low = tilelow[tile];
high = tilehigh[tile];
assert(high >= low);
if (high > low) {
	lbounds[n_intervals] = low;
	hbounds[n_intervals] = high;
	n_intervals++;
}
	}

	qsort(lbounds, n_intervals, sizeof(int), compare_int);
	qsort(hbounds, n_intervals, sizeof(int), compare_int);

	/*
	 * Now find a non-trivial point which is not an internal point
	 * of any given interval. At such points we can safely cut the
	 * floor piece without breaking any tiles.
	 * NOTE that this algorithm does NOT work if the set contains
	 * empty intervals, that's why we explicitly leave them out.
	 */

	i = 0;
	j = 0;
	cut = -1;
	/* Scan interval bounds in order */
	while (i < n_intervals && j < n_intervals) {
/* We prefer closing an interval over opening a new one */
if (lbounds[i] < hbounds[j])
	i++;
else
	j++;
assert(i >= j);
/* If there are no open intervals, we have a safe cut point */
if (i == j) {
	cut = hbounds[j-1]; 
	break;
}
	}

	/* Return failure if no cut point was found */
	if (cut == -1)
return 0;

	/*
	 * Ok, so now just split tile-set of this piece according
	 * to the cut coordinate.
	 */

	/* Re-arrange the tiles_by_piece array to separate the two pieces */
	i = offs;
	j = offs + n - 1;
	while (i <= j) {
/* Sweep i from start to end until we see a misplaced tile */
while (i <= j && tilehigh[tiles_by_piece[i]] <= cut)
	i++;
/* Sweep j from end to start until we see a misplaced tile */
while (i <= j && tilelow[tiles_by_piece[j]] >= cut)
	j--;
/* Swap the out-of-place tiles */
if (i < j) {
	int ti = tiles_by_piece[i];
	int tj = tiles_by_piece[j];
	tiles_by_piece[i] = tj;
	tiles_by_piece[j] = ti;
	i++;
	j--;
}
	}

	/* A bit of loop invariant magic proves that we can now safely
	   split the tile-set at index i */
	newoffs = i;
	assert(newoffs > offs && newoffs < offs + n);

	/* Update piece administration */
	newpiece = npieces++;
	piece_ntiles[piece] = newoffs - offs;
	piece_offset[newpiece] = newoffs;
	piece_ntiles[newpiece] = n + offs - newoffs;

	/* Recompute areas */
	fix_piece_area(piece);
	fix_piece_area(newpiece);

	/* Check that I didn't mess it up */
	for (i = 0; i < piece_ntiles[piece]; i++)
assert(tilehigh[tiles_by_piece[offs+i]] <= cut);
	for (i = 0; i < piece_ntiles[newpiece]; i++)
assert(tilelow[tiles_by_piece[newoffs+i]] >= cut);

	/* Return success */
	return 1;
}


/*
 *  Cut this piece if possible. Return 1 if the cut was succesful.
 */
int try_cut_piece(int piece)
{
	if (try_cut_piece_1d(piece, 0))
return 1;
	if (try_cut_piece_1d(piece, 1))
return 1;
	return 0;
}
void solve(void)
{
	int i, largest_piece;
	npieces = 1;
	piece_offset[0] = 0;
	piece_ntiles[0] = ntiles;
	for (i = 0; i < ntiles; i++)
tiles_by_piece[i] = i;
	fix_piece_area(0);
	while (1) {
largest_piece = 0;
for (i = 1; i < npieces; i++)
	if (piece_area[i] > piece_area[largest_piece])
largest_piece = i;
if (! try_cut_piece(largest_piece))
	break;
	}
	best_area = piece_area[largest_piece];
}
void write_output(void)
{
	printf("%d\n", best_area);
}
int main(void)
{
	int nfloor, i;
	scanf("%d\n", &nfloor);
	for (i = 0; i < nfloor; i++) {
read_input();
solve();
write_output();
	}
	return 0;
}

0

2

Месяц назад , нужно было изготовить Штампы . По совету знакомых бизнеспартнеров которые уже пользовались услугами фирмы
ppoligraf.ru решил и я позвонить им.
Сразу скажу мне очень понравилось,я не разочаровался.
Стоимость вышла та, что и обговаривали с менеджером,  я остался очень доволен и теперь всем их рекомендую, да и в целом, цены в печатнике доступные. Вообщем, рекомендую!

0

3

forex rubel dollar

#BURAGURU1957@@

0