K членов Жюри Десятой Всероссийской олимпиады школьников по информатике решили отметить столь круглую годовщину в одном из лучших ресторанов на Невском проспекте. На десерт вниманию Жюри предложили торт, имеющий форму прямоугольной призмы с выпуклым N-угольником в основании. Жюри вооружается десертными ножами и собирается справедливо разделить торт на K частей равного объема. Ножами можно проводить прямые вертикальные разрезы от одной границы торта до другой; различные разрезы могут иметь общие точки лишь в своих концевых вершинах.

Напишите программу, помогающую членам Жюри построить требуемые K-1 разрезов.

Входные данные
В первой строке входного файла содержатся два целых числа K и N (1 ≤ K, N ≤ 50). Далее следуют N пар вещественных чисел – координаты
последовательно расположенных вершин N-угольника.

Выходные данные
Каждый из K-1 разрезов в выходном файле должен быть представлен четверкой чисел – координатами своих концов. Все числа должны быть разделены пробелами и/или символами перевода строки.

Пример входного файла
4 3
2 1
0 0.5
4 0.5

Пример выходного файла
2 1 1 0.5
2 1 2 0.5
2 1 3 0.5

   Решение

Страница: 1 [Всего задач: 4]      

Какое минимальное количество спичек необходимо для того, чтобы выложить на плоскости N квадратов со стороной в одну спичку? Спички нельзя ломать и класть друг на друга. Вершинами квадратов должны быть точки, где сходятся концы спичек, а сторонами - сами спички.

Напишите программу MATCHES, которая по количеству квадратов N, которые необходимо составить, находит минимальное необходимое для этого количество спичек.

Единственная строка входного файла MATCHES.DAT содержит одно целое число N (1≤N≤10⁹).

Единственная строка выходного файла MATCHES.SOL должна содержать одно целое число - минимальное количество спичек требуемых для составления заданного количества квадратов.

Прислать комментарий

Решение

K членов Жюри Десятой Всероссийской олимпиады школьников по информатике решили отметить столь круглую годовщину в одном из лучших ресторанов на Невском проспекте. На десерт вниманию Жюри предложили торт, имеющий форму прямоугольной призмы с выпуклым N-угольником в основании. Жюри вооружается десертными ножами и собирается справедливо разделить торт на K частей равного объема. Ножами можно проводить прямые вертикальные разрезы от одной границы торта до другой; различные разрезы могут иметь общие точки лишь в своих концевых вершинах.

Напишите программу, помогающую членам Жюри построить требуемые K-1 разрезов.

Входные данные
В первой строке входного файла содержатся два целых числа K и N (1 ≤ K, N ≤ 50). Далее следуют N пар вещественных чисел – координаты
последовательно расположенных вершин N-угольника.

Выходные данные
Каждый из K-1 разрезов в выходном файле должен быть представлен четверкой чисел – координатами своих концов. Все числа должны быть разделены пробелами и/или символами перевода строки.

Пример входного файла
4 3
2 1
0 0.5
4 0.5

Пример выходного файла
2 1 1 0.5
2 1 2 0.5
2 1 3 0.5

Прислать комментарий

Решение

Задана квадратная доска размером N×N. Известно, что на ней играли в интеллектуальную игру, вследствие чего клеточки оказались окрашенными в белый, чёрный и зеленый цвета. Раскраска клеточек может быть разной (ведь это интеллектуальная игра!), но все клеточки самого верхнего ряда белые, а самого нижнего - чёрные.

Напишите программу SCORE, которая по раскраске квадрата находит количество клеточек в белой и чёрной областях.

Первая строка входного файла SCORE.DAT содержит единственное целое число N - размер квадрата (5≤N?250). Каждая из следующих N строк содержит по N символов "G", "W" или "B" (записанных без пробелов), которые обозначают зелёный, белый и чёрный цвет, соответственно.

Первая строка выходного файла SCORE.SOL должна содержать количество клеточек в белой области, а вторая строка - количество клеточек в чёрной области.

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

SCORE.DAT	SCORE.SOL
7 WWWWWWW WGWWBWG WWWWGWW BBGWWWB GWBBWGB BBBBGBB BBBBBBB	22 15

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

Прислать комментарий

Решение

---

Задача 102935  [Пересечение многоугольников ]

Темы:   [ Прямая и отрезок ] [ Площадь ]

Сложность: 3+

Два многоугольника на плоскости заданы координатами своих вершин. Требуется вычислить площадь пересечения этих многоугольников, то есть сумму площадей тех кусков, которые образуются при их пересечении и принадлежат каждому из них. При этом вы можете предполагать, что: 
    А) Многоугольники выпуклые, а координаты их вершин даны в произвольном порядке.
    Б) Хотя бы один из многоугольников невыпуклый, но известно, что у каждого из многоугольников не более одного угла, большего 180 градусов, а координаты вершин даны в порядке обхода по часовой стрелке.
Ваша программа по входным данным должна сама определить, какой из этих двух случаев имеет место.

Входные данные
Первая строка входного файла содержит целое число N – количество вершин в первом многоугольнике (3 ≤ N ≤ 50). Во второй строке записаны координаты этих вершин. Третья и четвертая строки таким же образом задают второй многоугольник. Координаты всех вершин являются целыми числами из диапазона [-32768, 32767].

Выходные данные
Выведите в выходной файл искомую площадь не менее чем с 6 верными значащими цифрами.

Пример входного файла
3
0 3 0 -3 -3 0
5
-1 1 2 1 1 0 2 -1 -1 -1

Пример выходного файла
2.0

Прислать комментарий

Решение

---

Страница: 1 [Всего задач: 4]      

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями