[ Обновленные темы · Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Задачи
eXceedДата: Понедельник, 18.01.2010, 15:24 | Сообщение # 1
Генералиссимус
Группа: Гости
Сообщений: 5466
Репутация: 616
Статус: Offline
Дано N квадратов на плоскости (1 < N < 100), причем стороны квадратов параллельны осям координат. Определить площадь области, которую определяют эти квадраты в совокупности (точка принадлежит этой области, если она находится хотя бы в одном из квадратов).
Формат входных данных
В первой строке входного файла находится число N.
В последующих N строках находятся тройки чисел (x, y, a), каждая из которых описывает один квадрат следующим образом: (x,y) - координаты центра квадрата, a - длина его стороны. Все числа - целые. -30000 < x,y < 30000. 0 < a < 1000.
Формат выходных данных
В выходной файл следует вывести площадь области, покрытой данными квадратами. Округлить значение до сотых и вывести ровно два знака после десятичной точки.
Пример ввода
3
0 0 2
1 1 2
-3 1 5
Правильный вывод для примера
31.00

В качестве решения пойдет и алгоритм. Это для тех, кто не умеет программировать.


bda-expert.ru — это система форумов, где можно общаться быстро и свободно, где любая точка зрения имеет право на жизнь.
 
zhylikДата: Пятница, 14.01.2011, 15:19 | Сообщение # 2
Подполковник
Группа: Гости
Сообщений: 146
Репутация: 30
Статус: Offline
Можно сначала:
1. Собрать в 1-й массив ординаты левой-верхней точки, правой-нижней точек, всех квадратов.
2. Отсортировать их по возрастанию.
3. Собрать в 2-й массив абсциссы левой-верхней точки, правой-нижней точек, всех квадратов. Этот массив должен состоять из записи типа [абсцисса, является_левой_или_правой, ордината_нижней_стороны_квадрата, ордината_верхней_стороны_квадрата]
4. Отсортировать 2-й массив по возрастанию значения абсциссы.

Потом разбить плоскость на горизонтальные куски (между двумя "соседними по массиву" ординатами). И вычислить площадь каждого такого куска.

Площадь куска вычисляется так:
Для каждого горизонтального куска:
- Определяем все квадраты, части которых которые содержатся в куске. Для этого перебираем все абсциссы и отфильтровываем те, у которых сохраненные в массиве ординаты верхней и нижней сторон квадрата влазиют в рамки куска.
- Для оставшихся абсцисс используем след. алгоритм (см. нижнюю часть рисунка, двигаться слева-направо).

Code

Открытые = 0;
XСтартовая = 0;
Площадь = 0;
ВысотаКуска = ...;
Для (X in ОтфильтрованныйМассивАбсцисс) {
   Если (ЯвляетсяАбсциссойЛевойСтороныКвадрата(X)) {
     Если (Открытые == 0) {
       XСтартовая = X;
     }
     Открытые++;
   }  
   Иначе {
     Открытые--;
     Если (Открытые == 0) {
       Площадь += ВысотаКуска*(X-XСтартовая);
     }
   }
}

кодик на JS во вложении. вроде щитает. проверок входных данных нету. говнокодик?)

Прикрепления: 9808696.png (2.2 Kb) · wowow.html (4.2 Kb)


Ваня Жилин ("zhylik" читается как жулик))
 
  • Страница 1 из 1
  • 1
Поиск:

close