| ← Март 2013 → | ||||||
|
1
|
2
|
3
|
||||
|---|---|---|---|---|---|---|
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
|
18
|
19
|
20
|
21
|
22
|
23
|
|
|
25
|
26
|
28
|
29
|
30
|
31
|
|
За последние 60 дней ни разу не выходила
Сайт рассылки:
http://prog.rusfaq.ru/C
Открыта:
14-03-2002
Статистика
0 за неделю
RFpro.ru: Программирование на C / C++
Хостинг портала RFpro.ru: РАССЫЛКИ ПОРТАЛА RFPRO.RU
Лучшие эксперты по данной тематике
/ КОМПЬЮТЕРЫ И СОФТ / Программирование / C/C++
Консультация # 187223: Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос: Требуется решить задачу,такого рода: Строительная компания приобрела участок земли - прямоугольное поле размером N * M сек- торов. После проведения геологических исследований выяснилось, что на поле есть K непригодных для строительства секторов. Необходимо построи... Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:
Дата отправки: 24.03.2013, 16:48 Консультирует Александр Чекменёв (Профессор): Здравствуйте, Иванов Д.И.! Код :
#include <iostream>
#include <list>
typedef unsigned long Int;
class Point
{
public:
Int x;
Int y;
Point(Int _x, Int _y) : x(_x), y(_y) {}
/*friend std::ostream & operator << ( std::ostream & os, const Point & p )
{
os << "(" << p.x << "," << p.y << ")";
return os;
}*/
};
class Rect
{
public:
Point lt; // left top
Point rb; // right bottom
Rect(const Point & _lt, const Point & _rb) : lt(_lt), rb(_rb) {}
/*friend std::ostream & operator << ( std::ostream & os, const Rect & r )
{
os << "[" << r.lt << ", " << r.rb << "]";
return os;
}*/
};
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);
}
// точка должна лежать внутри прямоугольника
std::list<Rect> breakRect(const Rect & r, const Point & p)
{
std::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);
}
/*void printRects(const std::list<Rect> & rs)
{
std::list<Rect>::const_iterator it = rs.cbegin();
while (it != rs.cend())
{
std::cout << *it++ << std::endl;
}
std::cout << std::endl;
}*/
int main()
{
Int N, M, K;
std::cin >> N >> M >> K;
// список прямоугольников
std::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;
std::cin >> x >> y;
Point p(x, y);
// смотрим, не надо ли разбить что-то из имеющихся прямоугольников
std::list<Rect>::iterator it = rs.begin();
while (it != rs.end())
{
Rect r = *it; // текущий прямоугольник
// если точка внутри прямоугольника -- надо бить
if (pointInRect(p, r))
{
std::list<Rect> broken = breakRect(r, p);
rs.splice(it, broken);
rs.erase(it++);
}
else
{
++it;
}
}
//printRects(rs);
}
// чистим список прямоугольников от прямоугольничков, содержащихся в больших
std::list<Rect>::iterator itBig = rs.begin();
while (itBig != rs.end())
{
Rect big = *itBig; // прямоугольник, в который будем пытаться вмещать остальные
std::list<Rect>::iterator it = rs.begin();
while (it != rs.end())
{
// сам с собой проверять нечего
if (it == itBig)
{
++it;
continue;
}
Rect r = *it; // прямоугольник, который постараемся выкинуть, как слишком маленький
if (into(r, big))
rs.erase(it++);
else
++it;
}
++itBig;
}
std::cout << rs.size() << std::endl;
//printRects(rs);
}
Оценить выпуск | Задать вопрос экспертам
главная страница
|
стать участником
|
получить консультацию
© 2001-2012, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про" Калашников О.А. | Гладенюк А.Г. Хостинг: Версия системы: 2011.6.36 от 26.01.2012 |
| В избранное | ||
