Прямоугольная детская площадка полностью замощена N плитками. Все плитки прямоугольные, возможно разного размера. Плитки не перекрываются.
На этой площадке решили построить песочницу. Чтобы подготовить место для песочницы, необходимо вынуть не более K плиток таким образом, чтобы песочница занимала все освободившееся пространство, была прямоугольной и имела максимально возможную площадь.
Напишите программу, которая определяет расположение песочницы, удовлетворяющей перечисленным выше требованиям.
Формат входных данных
Введем систему координат так, чтобы начало координат совпадало с одним из углов площадки, а оси координат шли вдоль сторон площадки. В этом случае противоположный угол площадки окажется в точке (X,Y).
Первая строка входного файла содержит два числа X и Y (натуральные числа, не превышающие 10000). Во второй строке заданы числа N и K (1<=K<=N<=2000). Следующие N строк файла содержат по четыре целых числа Xi,1, Yi,1, Xi,2, Yi,2, задающих координаты двух противоположных углов плитки (0<=Xi,1<Xi,2<=X, 0<=Yi,1<Yi,2<=Y).
Формат выходных данных
В выходной файл выведите координаты двух противоположных углов найденного прямоугольника. Если решений несколько, выведите любое из них.

Вход:
7 5
8 3
0 0 2 1
2 0 4 1
0 1 1 3
1 1 4 3
0 3 4 4
0 4 6 5
4 0 6 4
6 0 7 5

Выход:
0 1 4 4 - координаты
12 - площадь
3 кол-во плиток

Я вот, например, создавал прямоугольник с началом в начале одного из прямоугольников, а конец в конце другого. Проблема посчитать кол-во прямоугольников внутри моего. Если перебором, то долго получается. У меня есть мое решение (на си) и еще три решения от жюри (на паскале). Как эти три работают – фиг их знает. Еще есть пятнадцать тестов с ответами к ним. Если хотите, могу прислать архив. Еще раз уточняю вопрос: как посчитать кол-во прямоугольников внутри моего, если оптимизировать?

P. S.
Задача довольно известная.
Добавлено @ 20:23
В этом примере не проблема. А когда 1000 плиток из 2000 вынуть надо - тогда тормозно.
Добавлено @ 20:24
А это мой фиговый код на си:

Код

#include <stdio.h> #include <stdlib.h> #include <math.h> typedef struct tagRCT { int x; int y; } RCT; typedef struct tagRECT { int x, y, dx, dy; } RECT; int getnum(FILE* fp) { char buf[10]; int i = 0; while (1) {      buf[i] = fgetc(fp);      buf[i+1] = 0;      if ((buf[i] == ' ')||(buf[i] == 10)||   (buf[i] == 13)||(buf[i] == EOF))   return atoi(buf);      i++; } } void loadfile(char* fname, RECT** MRctso, RCT** MRctsd, int *X, int* Y, int *K, int* S) { FILE* fp = NULL; int n, n1; fp = fopen(fname, "r"); if (!fp) return; *X = getnum(fp); *Y = getnum(fp); *K = getnum(fp); *S = getnum(fp); RECT* Rctso = new RECT[*K]; RCT* Rctsd = new RCT[*K]; for (int i = 0; i < *K; i++) {  Rctso[i].x  = getnum(fp);  Rctso[i].y  = getnum(fp);  n  = getnum(fp);  n1 = getnum(fp);  Rctso[i].dx = n;  Rctso[i].dy = n1;  Rctsd[i].x = n;  Rctsd[i].y = n1; } (*MRctso) = Rctso; (*MRctsd) = Rctsd; fclose(fp); } void writefile(char* fname, RECT Rct, int t, int C) { char buf[10]; FILE* fp = fopen(fname, "w"); itoa(Rct.x, buf, 10); fputs(buf, fp); fputs(" ", fp); itoa(Rct.y, buf, 10); fputs(buf, fp); fputs(" ", fp); itoa(Rct.dx, buf, 10); fputs(buf, fp); fputs(" ", fp); itoa(Rct.dy, buf, 10); fputs(buf, fp); fputs("\n", fp); itoa(t, buf, 10); fputs(buf, fp); fputs("\n", fp); itoa(C, buf, 10); fputs(buf, fp); fclose(fp); } int cmpmax(const void* Rc1, const void* Rc2) { RCT* R1 = (RCT*)Rc1; RCT* R2 = (RCT*)Rc2; if ((R1->x>=R2->x)&&(R1->y>=R2->y)) return 1; return -1; } int cmpmin(const void* Rc1, const void* Rc2) { RCT* R1 = (RCT*)Rc1; RCT* R2 = (RCT*)Rc2; int s1 = R1->x*R1->y; int s2 = R2->x*R2->y; if (s1>s2) return -1; return 1; } void sort(RECT* Rcts, int K, int type = 1) { if (type)  qsort(Rcts, K, sizeof(RECT), cmpmax);  else  qsort(Rcts, K, sizeof(RCT), cmpmin); } void main() { RECT CurRect, MRect; RECT *Rctso = NULL; RCT *Rctsd = NULL; int Count = 0, X, Y, K, S, MS = 0, t, nm = 0, ns = 0, i, j, ii = 0, MC; loadfile("input.txt", &Rctso, &Rctsd, &X, &Y, &K, &S); //загружаем в два массивва if (!Rctso) return; // в первом начала и концы, в другом концы. if (S == 0) // если можно вынуть все плитки думать не надо {  MRect.x = 0;  MRect.y = 0;  MRect.dx = X;  MRect.dy = Y;  printf("Got one! #%i Count = %i S = %i\n", 1, K, X*Y);  writefile("output.txt", MRect, X*Y, K);  return; } sort(Rctso, K, 1); //сортируем начала по возрастанию, а sort((RECT*)Rctsd, K, 0); //концы по убыванию. Осталось от старой версии. for (i = 0; i < K; i++) {  CurRect.x = Rctso[i].x;    CurRect.y = Rctso[i].y; // выбираем начало моего прямоугольника    for (j = K-1; j > i; j--)    {     CurRect.dx = Rctso[j].dx;     CurRect.dy = Rctso[j].dy; // и его конец     if ((CurRect.dx < CurRect.x)||  // если неправильный прямоуг            (CurRect.dy < CurRect.y)) // пропускаем ход       continue;             //не уверен в правильности проверки   t = abs(CurRect.dx-CurRect.x);   t *= abs(CurRect.dy-CurRect.y); // считаем площадь     if (t > MS) // если площадь больше,   {       ns = 0;       Count = 0;       for (ii = i; ii < K; ii++) //считаем количество прямоугов внутри моего методом    {                          //полного перебора. Тут все тормоза и начинаются     if (CurRect.x <= Rctso[ii].x)           if (CurRect.y <= Rctso[ii].y)            if (CurRect.dx >= Rctso[ii].dx)              if (CurRect.dy >= Rctso[ii].dy)        {        Count++;           ns += abs((Rctso[ii].dx-Rctso[ii].x)*(Rctso[ii].dy-Rctso[ii].y));           if (Count == S) break; // если уже хватает прямоугов, выходим из поиска           if (Count > S) // а это уже слишком           {            ns = 0;         Count = 0;            break;           }           if (ns >= t) break; //суммарная площадь больше моего - ненадо такого        }     if (CurRect.dx < Rctso[ii].x)            if (CurRect.dy < Rctso[ii].y)       break; //если забрели далеко - можно не продолжать       }     if (ns != t) Count = 0; // если не совпало - что-то не влезло целиком.       if ((Count)&&(Count <= S)) // подводим итог       {        MS = t;       MRect = CurRect; //есть один. УРАААААА! только долго искали.        MC = Count;        nm++;        printf("Got one! #%i Count = %i S = %i\n", nm, Count, t);     //break;       }     }  } } delete[] Rctso; delete[] Rctsd; if (MS) writefile("output.txt", MRect, MS, MC); // пишем ответ }

Это сообщение отредактировал(а) Fixin - 19.2.2005, 20:53

Ну так какие будут варианты решений по обеим задачам? Вот эта кажется интереснее.

Энтузиастов полон двор.... у всех "мысля горит", аж прожигает всё.

Извини, сейчас маленько не до этого...
Что бы мозги задачу проще усваивали, пиши внятно.

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

Собстна где ты застопорился?

Краз на скорости застопорился. Последние варианты - боле-меня нормально. Срок - 3 сек при 2000 элементов. Моя - от 3 до 10.
Поблема в подсчете прямоугов внутри искомого.
В скорости.
Мысля у тебя хорошая. Счас новую версию закатаю.

Это сообщение отредактировал(а) Fixin - 19.2.2005, 20:52