Темы --> Информатика --> Алгоритмы --> Вычислительная геометрия --> Элементарная геометрия
---> 31 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: 1 2 3 4 5 6 7 >> Отображать по:
#457
Неподвижная точка карты
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Первый учебный день шестиклассника Пети начался с урока географии. Учитель объяснял классу, что перед тем, как изучать просторы нашей Родины, нужно научиться пользоваться географическими картами. Было также упомянуто и о том, что такое масштаб карты. В качестве домашней работы Пете и его одноклассникам задали нарисовать план (карту) своей комнаты, соблюдая масштабирование. Петю очень заинтересовало задание учителя, и поэтому, как только он пришел из школы домой, он принялся рисовать план. Это занятие было очень увлекательным, но вскоре с работы пришла Петина мама, сказала, что здоровье превыше всего и позвала его обедать. Во время обеда она по пути на кухню зашла в Петину комнату и решила, что ее надо проветрить. Для этого она открыла окно, перед которым стоял Петин стол.

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

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

Входные данные

Комната Пети и ее план имеют форму прямоугольника. Первая строка входного файла содержит два вещественных числа: ширину X и длину Y комнаты Пети (1≤X≤1000, 1≤Y≤1000). Комната расположена в декартовой прямоугольной системе координат так, что углы комнаты расположены в точках с координатами (0,0), (X,0), (X,Y), (0,Y).

Вторая строка содержит восемь вещественных чисел, описывающих положение углов плана комнаты в той же самой системе координат. Сначала задаются координаты того угла плана, который соответствует углу комнаты с координатами (0,0), затем — (X,0), (X,Y), наконец, (0,Y). Гарантируется, что входные данные корректны, то есть план является прямоугольником, линейные размеры плана находятся в полном соответствии с линейными размерами комнаты, план не выходит за границы комнаты.

Все числа во входном файле вещественные, заданы с точностью 5 знаков после десятичной точки. План выполнен в масштабе не менее 0.0001 и не более 1. Масштаб не может быть равен 1. Карта расположена лицевой стороной вверх.

Выходные данные

В первую строку выходного файла выведите 2 вещественных числа — координаты неподвижной точки плана и пола. Ответ нужно выдать с 3 знаками после десятичной точки.

Примеры
Входные данные
10.00000 5.00000
3.00000 2.50000 1.00000 2.50000 1.00000 1.50000 3.00000 1.50000
Выходные данные
2.500 2.083
#488
Найди прямую
  

Максимальное время работы на одном тесте:

2 секунды

Максимальный объем используемой памяти:

64 мегабайта

На плоскости дано множество отрезков. Требуется найти прямую, которая пересекла бы наибольшее возможное количество из данных отрезков и при этом проходила бы как минимум через две точки с целочисленными координатами.

Считается, что прямая пересекает отрезок, если она имеет с ним хотя бы одну общую точку (т.е. она может проходить через конец отрезка, внутреннюю точку отрезка, либо содержать весь отрезок).

Формат входных данных

Сначала вводится число N — количество отрезков (1≤N≤1000). Далее идет N четверок чисел Xi1, Yi1, Xi2, Yi2 задающих координаты концов отрезков. Все эти числа целые, по модулю не превосходящие 10000.

Заданные отрезки могут пересекаться, иметь общие части, один из них может полностью содержаться внутри другого. Отрезки имеют ненулевую длину.

Формат выходных данных

Выведите координаты каких-нибудь двух точек, через которые проходит прямая, пересекающая наибольшее количество отрезков. Координаты точек должны быть целыми и не должны по модулю превышать 107.

Примеры

Входные данные

Выходные данные

Пояснение

(кол-во отрезков, пересекаемых прямой)

3
0 0 1 0
0 1 1 1
0 2 1 2

0 -1 1 4

3

2
0 0 1 0
0 0 1 0

0 0 1 0

2

2
0 0 1 0
2 0 1 0

1 0 1 1

2

5
-1 0 3 4
2 3 5 6
0 2 2 -2
8 5 9 2
8 5 9 2

10 3 1 4

4
#493
Формула - 3
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Топологическая сортировка

В ежегодном чемпионате Флатландии (которая, естественно, является плоским миром) по космическим гонкам "Формула-3" участвуют N космических скутеров, имеющие форму треугольников. До начала гонок скутеры занимают положение в стартовой зоне согласно результатам жеребьевки.

1

Скутеры стартуют строго по порядку. Каждый скутер,получив команду «старт», уезжает в положительном направлении оси Ox. Следующий скутер стартует лишь тогда, когда предыдущий покинет стартовую зону. Скутеры уезжают строго параллельно оси Ox, скутеры в стартовой зоне не поворачивают и не разворачиваются.

Естественно, что если в момент старта на пути скутера окажется другой скутер, то произойдет авария (даже если скутер заденет лишь угол другого скутера своим углом).

Для уменьшения опасности столкновения скутеров на старте строго соблюдается следующее правило: прямые, параллельные оси Ox и пересекающие какой-то скутер, должны в совокупности пересекать не более 100 других скутеров (прямая, проходящая через одну точку скутера также считается прямой, пересекающей скутер). Например, на приведенном рисунке прямые, параллельные Ox и пересекающие скутер 2, проходят через 2 других скутера (1 и 3), а прямые, проходящие через скутер 1, проходят только через один другой скутер (номер 2).

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

Помогите Главному Судье — напишите программу, которая определит какой-нибудь порядок старта скутеров, чтобы аварии не произошло.

Входные данные

В первой строке вводится натуральное число N( 1 ≤ N ≤ 30 000).

В каждой из следующих N строк содержится по 6 чисел: x1, y1, x2, y2, x3, y3 – координаты трех вершин скутера на старте, целые числа, не превосходящие по модулю 106. В начальный момент скутеры не задевают друг друга.

Выходные данные

Выведите через пробел N чисел – номера скутеров в том порядке, в котором они могут стартовать. Если решений несколько, выведите одно любое из них. Если решений нет, выведите одно число -1.

Примечание: первый тест соответствует приведенному рисунку. Ответ 2 3 1 в этом тесте также является правильным

Примеры
Входные данные
3
1 19 3 9 6 15
5 6 10 2 10 12
1 1 6 1 3 7
Выходные данные
Входные данные
3
0 1 -2 1 -1 -1
5 6 10 2 10 12
1 1 6 1 3 7


Выходные данные

                            
                                


                        

                    

                    

                        

                            

                                #496
                            

                            

                                Точки
                            

                              
                
                            

                                
                                
                            


                        

                        

                                

                                

                                    

                                        
ограничение по времени на тест

                                        2.0 second;
                                    
                                        
ограничение по памяти на тест

                                        64 megabytes
                                    

                                

                            
                            

   




Петя и Вася играют в "точки". Петя отметил на клетчатом листе бумаги несколько точек – узлов сетки. Вася хочет окружить их многоугольником так, чтобы все отмеченные узлы лежали строго внутри (не на границе) этого многоугольника и чтобы все стороны этого многоугольника проходили только по сторонам или диагоналям клеток сетки, а его периметр был минимально возможным. Определите, чему равен периметр такого многоугольника.


   


   

    

     Входные данные
    




В первой строке входных данных содержится число N – количество отмеченных Петей точек (1 ≤ N ≤ 100 000). 



В каждой из следующих N строк записаны по два числа xi, yi – координаты точек, нарисованных Петей. Координаты по абсолютной величине не превосходят 106. Некоторые точки могут совпадать.


   


   

    

     Выходные данные
    




Требуется вывести одно число – периметр искомого многоугольника. Ответ нужно вывести с точностью не менее 0.001.



    

    



                            
Примеры
Входные данные
1
0 0

Выходные данные
5.6568542495

Входные данные
2
1 1
1 2

Выходные данные
7.6568542495


                            
                                


                        

                    

                    

                        

                            

                                #715
                            

                            

                                Морской бой
                            

                              
                
                            

                                
                                
                            


                        

                        

                            
                                Заданы начальные координаты и скорости кораблей на плоскости. Есть бомбы, уничтожающие корабли на расстоянии не превышающем R от центра взрыва. Взрывать бомбы можно только в целые моменты времени. Требуется уничтожить все корабли наименьшим количеством бомб.

                            

   



  
N вражеских кораблей движутся прямолинейно с постоянными скоростями. Вакуумная бомба уничтожает все объекты в радиусе R от точки взрыва (то есть все объекты, расстояние от которых до точки взрыва не больше  R). Взрывать бомбу можно только в целые моменты времени.


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

   


   

    

     Входные данные
    




В первой строке входных данных задаются целые числа N (2 <= N <= 10) и R (0 < R ≤ 50. В следующих Nстроках  содержится по 4 числа, описывающих движение кораблей. Первые два числа строки – координаты корабля в момент времени 0, по модулю не превосходящие 105. Следующие два числа – значения координат вектора скорости, по модулю не превосходящие 1000. Все эти числа целые. 



Гарантируется, что никакие 2 корабля не имеют одинаковые векторы скорости.Однако вполне возможно, что в какой-то момент времени два корабля пройдут через одну точку.


   


   

    

     Выходные данные
    



 
В первой строке выведите одно число – минимальное количество взрывов K. В следующих K строках для каждого взрыва выведите по три числа: целое время взрыва и вещественные координаты взрыва, указанные с точностью не менее трех значащих цифр после точки. Разрешается производить взрывы как в разные, так и в один и тот же момент времени. Разрешается взрывы производить как в различных точках, так и в одной точке в разные моменты времени. 


 
Если решений несколько, выведите любое из них. 


 
 Комментарий.  Решения, верно работающие при N ≤ 3, будут набирать не менее 50 баллов. 



   

   


                            
Примеры
Входные данные
3 3
-3 3 1 0
0 -6 0 2
-8 6 4 -1

Выходные данные
1
3 2.000 1.500

Входные данные
2 1
-4 -4 2 2
2 2 -2 -2

Выходные данные
2
0 -4.0000 -4.0000
0 2.0000 2.0000


                            

                        

                    

                

                
        

            Страница: 
                    1
                    2
                    3
                    4
                    5
                    6
                    7
                >>
            Отображать по:
            
        

    
            

        

        
    
    

    

        

            
Выбрано
:
            
Отменить
|
            
Добавить в контест