Консультация № 187223
24.03.2013, 16:48
200.47 руб.
0 44 1
Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:
Требуется решить задачу,такого рода:
Строительная компания приобрела участок земли - прямоугольное поле размером N * M сек-
торов. После проведения геологических исследований выяснилось, что на поле есть K непригодных
для строительства секторов. Необходимо построить одно здание прямоугольной формы со сторо-
нами параллельными границам участка. Компания заинтересована в рациональном использовании
участка, поэтому границы здания должны упираться либо в непригодные для строительства секто-
ры, либо в границы участка. Сколько существует вариантов выбора места для строительства здания
на приобретенном участке?
Формат входного файла
В первой строке задаются размеры поля N, M (1 ≤ N, M ≤ 10^9) и количество непригодных
для строительства секторов K (1 ≤ K ≤ 500). В следующих K строках задаются координаты
непригодных секторов Xi, Yi (1 ≤ Xi ≤ N, 1 ≤ Yi ≤ M). Все числа во входных данных целые.
Формат выходного файла
Число вариантов выбора места для строительства здания.



P.S.
Имя входного файла stdin
Имя выходного stdout
Пример
на входе
3 4 2
2 3
3 2
результат
5

Среда разработки = консольное приложение,желательно turbo C++

Обсуждение

давно
Посетитель
396751
37
25.03.2013, 21:52
общий
если сделать так
typedef int BOOL
сразу куча ошибок
давно
Профессор
399103
482
25.03.2013, 21:54
общий
Адресаты:
Нашёл я TC3.0 -- там действительно bool не было. А шаблонов -- тем более, кстати.

У вас есть два варианта: руками заменить всё шаблонные параметры на конкретные, дописать typedef int bool; или собирать любым, не настолько древним компилятором.
давно
Профессор
399103
482
25.03.2013, 22:07
общий
Адресаты:
Собственно, вот: http://codepad.org/Qn1nsrUg
Как оттуда видно, g++ 4.1.2 собирает успешно.
давно
Посетитель
396751
37
25.03.2013, 22:29
общий
25.03.2013, 22:31
Цитата: 392175
руками заменить всё шаблонные параметры на конкретные, дописать typedef int bool


а что вы именили под этим?понятно то что должен дописать,а под руками заменять шаблонные параметры не понял



на codepad
cc1plus: warnings being treated as errors
In function 'int main(int, char**)':
Line 235: warning: format '%lu' expects type 'long unsigned int', but argument 3 has type 'size_t'
t.cpp: In constructor 'Node<T>::Node(const T&, Node<T>*, Node<T>*) [with T = Rect]':
t.cpp:52: instantiated from 'void List<T>::push_back(const T&) [with T = Rect]'
t.cpp:140: instantiated from here
Line 16: warning: 'Node<Rect>::_val' will be initialized after
Line 14: warning: 'Node<Rect>* Node<Rect>::_prev'
Line 19: warning: when initialized here
давно
Профессор
399103
482
25.03.2013, 22:44
общий
Адресаты:
Цитата: Иванов Д.И.
а под руками заменять шаблонные параметры не понял

Turbo C++ не умеет шаблоны. В этой программе от них можно избавиться.

Цитата: Иванов Д.И.
на codepad
cc1plus: warnings being treated as errors

Это предупреждения при самом строгом режиме компиляции. На то, что порядок объявления и инициализации членов класса не совпадают и на то, что size_t и unsigned long, вообще говоря, не тождественны.
давно
Посетитель
396751
37
25.03.2013, 23:00
общий
Цитата: 392175
Turbo C++ не умеет шаблоны. В этой программе от них можно избавиться.


Я извиняюсь за наглость, подскажите как избавиться,чтобы заработало в tc ?
давно
Профессор
399103
482
25.03.2013, 23:06
общий
Адресаты:
А почему бы просто не взять любой другой компилятор?
давно
Посетитель
396751
37
25.03.2013, 23:18
общий
я сам то взял уже давно,dev-c++, справляется на отлично, но там где это нужно, желают видеть на tc
давно
Посетитель
396751
37
26.03.2013, 12:16
общий
если Вас не затруднит,можете прокоментировать каждую строку кода?
давно
Профессор
399103
482
26.03.2013, 14:13
общий
Адресаты:
Цитата: Иванов Д.И.
там где это нужно, желают видеть на tc

Тогда постарайтесь избавиться от шаблонов. Всё равно используется список лишь прямоугольников.

Цитата: Иванов Д.И.
можете прокоментировать каждую строку кода?

Каждую?! Нет. Что именно неясно?
давно
Посетитель
396751
37
26.03.2013, 14:37
общий
26.03.2013, 14:38
Цитата: 392175
Каждую?! Нет. Что именно неясно?


не совсем ясно в коде:
1) Для чего класс Node, что делается в publice?
2) Класс Point
3)Класс Rect
давно
Профессор
399103
482
26.03.2013, 14:45
общий
Адресаты:
1. Node -- узел списка. В public лишь конструктор и геттеры.
2. Point -- точка. Содержит x и y на поле.
3. Rect -- rectangle -- прямоугольник на поле.
давно
Посетитель
396751
37
26.03.2013, 14:59
общий
Цитата: 392175
огда постарайтесь избавиться от шаблонов. Всё равно используется список лишь прямоугольников.


а как от них правильно избавиться,если классы node,list итд используют например node <t>итд
отдельно переписывать в функции?или как?можете пример привести?
давно
Профессор
399103
482
26.03.2013, 15:04
общий
Адресаты:
Ну, шаблоны зачем нужны? Чтобы переиспользовать код для разных типов. Т.е., функции -- это параметризация кода значением:
int sqr(int x) { return x*x; }
А шаблоны -- это параметризация ещё и типом:
template <class T>
T sqr(T x) { return x*x; }

В нашем случае написан класс списка, который может содержать элементы любых типов. А на деле используется только Rect. Т.о., грубо говоря, надо T заменить на Rect.
давно
Посетитель
396751
37
26.03.2013, 16:03
общий
Код:

//template <class T>
class Node
{
template <typename U>
friend class List;

Node<Rect>* _prev;
Node<Rect>* _next;
Rect _val;

public:
Node(const Rect& val, Node* prev, Node* next) : _val(val) , _prev(prev) , _next(next) {}

const Rect& val() { return _val; }

Node<Rect>* prev() { return _prev; }
Node<Rect>* next() { return _next; }
};


вы имели в виду так?
давно
Профессор
399103
482
26.03.2013, 16:30
общий
26.03.2013, 16:49
Адресаты:
Тепло. Угловых скобочек в этом фрагменте быть вообще не должно.
давно
Посетитель
396751
37
26.03.2013, 16:56
общий
Код:
//template <class T>
class Node
{
//template <typename U>
friend class List;

Node Rect* _prev;
Node Rect* _next;
Rect _val;

public:
Node(const Rect& val, Node* prev, Node* next) : _val(val) , _prev(prev) , _next(next) {}

const Rect& val() { return _val; }

Node Rect* prev() { return _prev; }
Node Rect* next() { return _next; }
};



так?
давно
Посетитель
396751
37
26.03.2013, 18:54
общий
Но конечно же и так ошибка.
Александр,можете подправить код?без шаблонов?не могу сообразить,как правильно сделать



P.S. Очень нужно
давно
Профессор
399103
482
26.03.2013, 19:02
общий
Адресаты:
Цитата: Иванов Д.И.
так?

Нет. Что, по-вашему, должно означать:
Node Rect* _prev;
?
Вместо этого
Node* _prev;
должно быть.

Цитата: Иванов Д.И.
можете подправить код?

Сейчас ни желания ни времени нет.
давно
Посетитель
396751
37
26.03.2013, 19:52
общий
26.03.2013, 19:53
Цитата: 392175
Нет. Что, по-вашему, должно означать:Node Rect* _prev;?Вместо этогоNode* _prev;должно быть.

Да,это уже понял, сделал, но как обойти строку
T _val;
?

потом в конструкторе же использование
const T& val.....
итд

давно
Профессор
399103
482
26.03.2013, 19:57
общий
Адресаты:
Цитата: Иванов Д.И.
Да,это уже понял, сделал, но как обойти строку
T _val;
?

Rect _val;

Идея же в том, что T теперь конкретное -- Rect. В связи с чем и Node конкретный -- просто Node.
давно
Посетитель
396751
37
26.03.2013, 20:03
общий
так уже пробовал,ошибка
так же?
Код:



//template <class Rect>
class Node
{
template <typename U>
friend class List;

Node* _prev;
Node* _next;
Rect _val;

public:
Node(const Rect& val, Node* prev, Node* next) : _val(val) , _prev(prev) , _next(next) {}

const Rect& val() { return _val; }

Node* prev() { return _prev; }
Node* next() { return _next; }
};


ошибка
16 H:\C++\main.cpp `Rect' does not name a type
давно
Профессор
399103
482
26.03.2013, 20:44
общий
Адресаты:
Цитата: Иванов Д.И.
так уже пробовал,ошибка
так же?

Похоже на правду. Компилятор на данном этапе не знает, что есть класс Rect. Можно объявить Rect до Node.
давно
Посетитель
396751
37
26.03.2013, 21:00
общий
Цитата: 392175
Похоже на правду. Компилятор на данном этапе не знает, что есть класс Rect. Можно объявить Rect до Node.



Вы имеете ввиду сам класс rect сделать первым?
давно
Профессор
399103
482
26.03.2013, 21:02
общий
Адресаты:
Да.
давно
Посетитель
396751
37
26.03.2013, 21:07
общий
Сделал, также пришлось ещё класс поинт выносить
получилось так:
Код:

#include <cstdlib>
#include <iostream>
#include <stdio.h>
#include <conio.h>

typedef unsigned long Int;

class Point
{
public:
Int x;
Int y;

Point(Int _x, Int _y) : x(_x), y(_y) {}
};

class Rect
{
public:
Point lt; // left top
Point rb; // right bottom

Rect(const Point & _lt, const Point & _rb) : lt(_lt), rb(_rb) {}
};

//template <class Rect>
class Node
{
// template <typename U>
friend class List;

Node* _prev;
Node* _next;
Rect _val;

public:
Node(const Rect& val, Node* prev, Node* next) : _val(val) , _prev(prev) , _next(next) {}

const Rect& val() { return _val; }

Node* prev() { return _prev; }
Node* next() { return _next; }
};

//template <class T>
class List
{
protected:
Node<Rect>* _first;
Node<Rect>* _last;
public:
List() : _first(0), _last(0) {}
~List()
{
Node* curr = begin();
while (curr != end())
{
Node* next = curr->next();
delete curr;
curr = next;
}
}

void push_back(const Rect& x)
{
// если список пуст
if (0 == _first)
{
_first = new Node<Rect>(x, 0, 0);
_last = _first;
}
// если нет -- добавляем в конец
else
{
Node* newNode = new Node(x, _last, 0);
_last->_next = newNode;
_last = newNode;
}
}

void erase(Node* node)
{
Node* curr = node;
if (curr != _first) curr->prev()->_next = curr->next();
if (curr != _last) curr->next()->_prev = curr->prev();
// если узел и начало и конец -- это единственный элемент списка
if (curr == _first && curr == _last) { _first = _last = 0; }
delete curr;
}

void insertFront(List& list)
{
// если список пуст, просто замещаем
if (0 == _first)
{
_first = list._first;
_last = list._last;
}
else
{
list._last->_next = _first;
_first->_prev = list._last;

_first = list._first;
}

list._first = list._last = 0;
}

Node* begin() { return _first; }
Node* end() { return 0; }

size_t size()
{
size_t s = 0;
for (Node* curr = begin(); curr != end(); curr = curr->next())
++s;
return s;
}
};





bool inbetween(Int x, Int a, Int b)
{
return a <= x && x <= b;
}

bool pointInRect(const Point & p, const Rect & r)
{
return inbetween(p.x, r.lt.x, r.rb.x)
&& inbetween(p.y, r.lt.y, r.rb.y);
}

// точка должны лежать внутри прямоугольника
List<Rect> breakRect(const Rect & r, const Point & p)
{
List<Rect> rs;

// если есть место слева
if (p.x > r.lt.x) rs.push_back(Rect(r.lt, Point(p.x-1, r.rb.y)));
// справа
if (p.x < r.rb.x) rs.push_back(Rect(Point(p.x+1, r.lt.y), r.rb));

// если есть место сверху
if (p.y > r.lt.y) rs.push_back(Rect(r.lt, Point(r.rb.x, p.y-1)));
// снизу
if (p.y < r.rb.y) rs.push_back(Rect(Point(r.lt.x, p.y+1), r.rb));

return rs;
}

// лежит ли первый прямоугольник во втором
bool into(const Rect & r, const Rect & big)
{
return pointInRect(r.lt, big)
&& pointInRect(r.rb, big);
}
using namespace std;

int main()
{
Int N, M, K;
fscanf(stdin, "%lu%lu%lu", &N, &M, &K);

// список прямоугольников
List<Rect> rs;
// вначале есть прямоугольник во всё поле
rs.push_back(Rect(Point(1,1), Point(N,M)));

//printRects(rs);

for (Int i = 0; i < K; ++i)
{
// препятствие
Int x, y;
fscanf(stdin, "%lu%lu", &x, &y);
Point p(x, y);

// смотрим, не надо ли разбить что-то из имеющихся прямоугольников
Node<Rect>* it = rs.begin();
while (it != rs.end())
{
Rect r = it->val(); // текущий прямоугольник
// если точка внутри прямоугольника -- надо бить
if (pointInRect(p, r))
{
List<Rect> broken = breakRect(r, p);
//rs.splice(it, broken);
rs.insertFront(broken);

Node<Rect>* next = it->next();
rs.erase(it);
it = next;
}
else
{
it = it->next();
}
}

//printRects(rs);
}

// чистим список прямоугольников от прямоугольничков, содержащихся в больших
Node<Rect>* itBig = rs.begin();
while (itBig != rs.end())
{
Rect big = itBig->val(); // прямоугольник, в который будем пытаться вмещать остальные

Node<Rect>* it = rs.begin();
while (it != rs.end())
{
// сам с собой проверять нечего
if (it == itBig)
{
it = it->next();
continue;
}

Rect r = it->val(); // прямоугольник, который постараемся выкинуть, как слишком маленький
if (into(r, big))
{
Node<Rect>* next = it->next();
rs.erase(it);
it = next;
}
else
{
it = it->next();
}
}

itBig = itBig->next();
}

fprintf(stdout, "%lu", rs.size());
cin.get();
getch();
return 0;


}




при компиляции
49 H:\C++\main.cpp `Node' is not a template
также остальные строки
давно
Профессор
399103
482
26.03.2013, 21:10
общий
Адресаты:
Цитата: Иванов Д.И.
также пришлось ещё класс поинт выносить

Разумеется.

Цитата: Иванов Д.И.
49 H:\C++\main.cpp `Node' is not a template

Разумеется. Здесь-то тоже шаблоны.
давно
Посетитель
396751
37
26.03.2013, 21:18
общий
Код:

#include <cstdlib>
#include <iostream>
#include <stdio.h>
#include <conio.h>

typedef unsigned long Int;

class Point
{
public:
Int x;
Int y;

Point(Int _x, Int _y) : x(_x), y(_y) {}
};

class Rect
{
public:
Point lt; // left top
Point rb; // right bottom

Rect(const Point & _lt, const Point & _rb) : lt(_lt), rb(_rb) {}
};

//template <class Rect>
class Node
{
// template <typename U>
friend class List;

Node* _prev;
Node* _next;
Rect _val;

public:
Node(const Rect& val, Node* prev, Node* next) : _val(val) , _prev(prev) , _next(next) {}

const Rect& val() { return _val; }

Node* prev() { return _prev; }
Node* next() { return _next; }
};

//template <class T>
class List
{
protected:
Node* _first;
Node* _last;
public:
List() : _first(0), _last(0) {}
~List()
{
Node* curr = begin();
while (curr != end())
{
Node* next = curr->next();
delete curr;
curr = next;
}
}

void push_back(const Rect& x)
{
// åñëè ñïèñîê ïóñò
if (0 == _first)
{
_first = new Node(x, 0, 0);
_last = _first;
}
// åñëè íåò -- äîáàâëÿåì â êîíåö
else
{
Node* newNode = new Node(x, _last, 0);
_last->_next = newNode;
_last = newNode;
}
}

void erase(Node* node)
{
Node* curr = node;
if (curr != _first) curr->prev()->_next = curr->next();
if (curr != _last) curr->next()->_prev = curr->prev();
// åñëè óçåë è íà÷àëî è êîíåö -- ýòî åäèíñòâåííûé ýëåìåíò ñïèñêà
if (curr == _first && curr == _last) { _first = _last = 0; }
delete curr;
}

void insertFront(List& list)
{
// åñëè ñïèñîê ïóñò, ïðîñòî çàìåùàåì
if (0 == _first)
{
_first = list._first;
_last = list._last;
}
else
{
list._last->_next = _first;
_first->_prev = list._last;

_first = list._first;
}

list._first = list._last = 0;
}

Node* begin() { return _first; }
Node* end() { return 0; }

size_t size()
{
size_t s = 0;
for (Node* curr = begin(); curr != end(); curr = curr->next())
++s;
return s;
}
};





bool inbetween(Int x, Int a, Int b)
{
return a <= x && x <= b;
}

bool pointInRect(const Point & p, const Rect & r)
{
return inbetween(p.x, r.lt.x, r.rb.x)
&& inbetween(p.y, r.lt.y, r.rb.y);
}

// òî÷êà äîëæíû ëåæàòü âíóòðè ïðÿìîóãîëüíèêà
List breakRect(const Rect & r, const Point & p)
{
List rs;

// åñëè åñòü ìåñòî ñëåâà
if (p.x > r.lt.x) rs.push_back(Rect(r.lt, Point(p.x-1, r.rb.y)));
// ñïðàâà
if (p.x < r.rb.x) rs.push_back(Rect(Point(p.x+1, r.lt.y), r.rb));

// åñëè åñòü ìåñòî ñâåðõó
if (p.y > r.lt.y) rs.push_back(Rect(r.lt, Point(r.rb.x, p.y-1)));
// ñíèçó
if (p.y < r.rb.y) rs.push_back(Rect(Point(r.lt.x, p.y+1), r.rb));

return rs;
}

// ëåæèò ëè ïåðâûé ïðÿìîóãîëüíèê âî âòîðîì
bool into(const Rect & r, const Rect & big)
{
return pointInRect(r.lt, big)
&& pointInRect(r.rb, big);
}
using namespace std;

int main()
{
Int N, M, K;
fscanf(stdin, "%lu%lu%lu", &N, &M, &K);

// ñïèñîê ïðÿìîóãîëüíèêîâ
List rs;
// âíà÷àëå åñòü ïðÿìîóãîëüíèê âî âñ¸ ïîëå
rs.push_back(Rect(Point(1,1), Point(N,M)));

//printRects(rs);

for (Int i = 0; i < K; ++i)
{
// ïðåïÿòñòâèå
Int x, y;
fscanf(stdin, "%lu%lu", &x, &y);
Point p(x, y);

// ñìîòðèì, íå íàäî ëè ðàçáèòü ÷òî-òî èç èìåþùèõñÿ ïðÿìîóãîëüíèêîâ
Node* it = rs.begin();
while (it != rs.end())
{
Rect r = it->val(); // òåêóùèé ïðÿìîóãîëüíèê
// åñëè òî÷êà âíóòðè ïðÿìîóãîëüíèêà -- íàäî áèòü
if (pointInRect(p, r))
{
List broken = breakRect(r, p);
//rs.splice(it, broken);
rs.insertFront(broken);

Node* next = it->next();
rs.erase(it);
it = next;
}
else
{
it = it->next();
}
}

//printRects(rs);
}

// ÷èñòèì ñïèñîê ïðÿìîóãîëüíèêîâ îò ïðÿìîóãîëüíè÷êîâ, ñîäåðæàùèõñÿ â áîëüøèõ
Node* itBig = rs.begin();
while (itBig != rs.end())
{
Rect big = itBig->val(); // ïðÿìîóãîëüíèê, â êîòîðûé áóäåì ïûòàòüñÿ âìåùàòü îñòàëüíûå

Node* it = rs.begin();
while (it != rs.end())
{
// ñàì ñ ñîáîé ïðîâåðÿòü íå÷åãî
if (it == itBig)
{
it = it->next();
continue;
}

Rect r = it->val(); // ïðÿìîóãîëüíèê, êîòîðûé ïîñòàðàåìñÿ âûêèíóòü, êàê ñëèøêîì ìàëåíüêèé
if (into(r, big))
{
Node* next = it->next();
rs.erase(it);
it = next;
}
else
{
it = it->next();
}
}

itBig = itBig->next();
}

fprintf(stdout, "%lu", rs.size());
cin.get();
getch();
return 0;


}



Сделал так,вроде работает, но иногда при расчете система завершает работу проги.
не знаю почему, из кода убрал там где были node<rect> итд, после всех таких заменах закомпилировал
давно
Профессор
399103
482
26.03.2013, 21:27
общий
Адресаты:
Цитата: Иванов Д.И.
иногда при расчете система завершает работу проги.
не знаю почему

Тоже не знаю. Эффект на первой программе, там где с STL, есть? Если да, скажите соответствующие примеры входных данных.
давно
Посетитель
396751
37
26.03.2013, 21:57
общий
Цитата: 392175
ффект на первой программе, там где с STL, есть?


в версии с stl нет
Форма ответа