Задача B. Хип

Задача B. Хип

Коля к рыбалке равнодушен, но иногда составляет Вале компанию. Однажды он предложил Вале вместо рыбалки погулять – пройти по тропинке дальше озера. Валя согласился, и друзья отправились в путешествие. Тропинка уводила их от озера дальше и дальше, то выбегая на опушку леса, то углубляясь в чащу. Ребята шли, оживленно разговаривая, пока путь им не преградили несколько поваленных деревьев. Искать обходной путь они не стали – для этого пришлось бы продираться через высокие колючие кусты, – а просто перелезли через завал. Пройдя еще немного, они очутились на большой поляне, где стояла низенькая, покосившаяся избушка. Возле избушки пропалывала грядки пожилая женщина в цветастом платке и длинной юбке в крупную клетку. Сначала она не заметила ребят, но их шаги разбудили дремавшего на крыльце большого серого кота. Кот тревожно замяукал, его хозяйка прервала работу, некоторое время пристально смотрела на Колю и Валю, потом подошла к ним поближе и негромко спросила:

– И куда же путь держите?

– Да мы гуляли просто… – замялся Коля, – Шли и шли по тропинке, а потом через завал перелезли.

– Так значит, у нашего доброго господина Маллока, да продлятся его дни, вновь свадьба? – спросила женщина.

– А кто такой этот Маллок? – поинтересовался Валя.

– Ему здесь подвластно все, – женщина говорила уже шепотом. – А вы и в самом деле пришли из-за Дальнего Рубежа? И Сканф пропустил вас?

– Мы по тропинке шли. Просто так, гуляли. И никого по дороге не видели, – тихо сказал Валя. – И про Дальний Рубеж тоже не знаем ничего.

– Мой сын много лет назад нашел дорогу за Дальний Рубеж, и ушел туда. Он иногда приходит, зовет меня к себе, но я привыкла здесь жить, – вздохнула женщина. – Да и избушка моя в Хип никогда почти и не попадает: и стоит на отшибе, и живу я одна…

– А что такое Хип? – Валя только сейчас заметил, что женщина обута в деревянные башмаки. Впрочем, по сравнению со всем происходящим, это обстоятельство казалось Вале наименее странным. – Расскажите нам, пожалуйста.

Женщина ненадолго задумалась, оглядела еще раз Валю и Колю и произнесла:

– Хорошо. Пойдемте в дом. Рейз нас предупредит, если что. Правда, Рейз? – она посмотрела на кота. Кот издал урчащий звук, всем своим видом выражая согласие.

Ребята вошли в избушку, уселись на лавку, и Валя снова спросил: «Так что же такое Хип?». Вот что они узнали.

Господин Маллок живет в Большом Замке Ксеон, который имеет форму параллелепипеда, стороны прямоугольника, лежащего в основании параллелепипеда, равны A и B. Его подданные живут в столь небольших домиках, что, по сравнению с замком, любой домик может считаться точкой. Могущество господина Маллока измеряется величиной M. Это могущество распространяется на всех подданных, чьи дома попадают внутрь прямоугольника, центр которого совпадает с центром замка, а стороны параллельны сторонам замка A и B и имеют размеры M*A и M*B соответственно. Собственно этот большой прямоугольник и именуют Хип. Маллок стремится, чтобы в Хип попало максимально возможное количество жителей. Он может поворачивать свой замок на любой целочисленный (в градусах) угол, но на поворот тратится часть его могущества. Ваша задача – определить для заданных исходных данных такое положение замка Маллока, чтобы количество жителей, попавших в Хип, оказалось максимально возможным.

Формат входного файла input.txt

Первая строка – целые числа N (1<= N <= 1000), A (1<=A<=100), B (1<=B<=100), M (1<=M<=1000), вещественное число P (0.01 <= P <= 0.99) через пробел.

N – количество домов подданных Маллока

A и B – длины сторон замка Маллока. В начальном положении сторона длины А параллельна оси абсцисс.

M – могущество Маллока

P – коэффициент, показывающий уменьшение могущества Маллока при повороте замка на 90⁰ (после поворота на такой угол могущество становится равным M*(1 – P)). Коэффициент

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

Каждая из следующих N строк содержит три целых числа: Xj (–100000 <= Xj <= 100000), Yj
(–100000 <= Yj <= 100000) и Kj (1 <= Kj <= 10) (j = 1, 2, …, N) через пробел.

Xj и Yj – координаты дома №j подданных Маллока в системе координат с центром в центре замка, осью X, параллельной стороне замка шириной A, и осью Y, параллельной стороне замка шириной B.

Kj – количество подданных, проживающих доме № j.

Формат выходного файла output.txt

Первая строка – целое число – максимально возможное количество подданных Маллока, оказавшихся в Хипе (точки на границе Хипа также считаются попавшими в Хип).

Вторая строка – целое число – минимальный (по модулю) угол, на который Маллоку следует повернуть свой замок. В случае если замок следует поворачивать по часовой стрелке, через пробел после числа выведите символ ‘R’ (без кавычек, разумеется), если же замок следует поворачивать против часовой стрелки, выведите через пробел после числа символ ‘L’ (также без кавычек).

Примечание. Если угол получился равным 90 или 0, то поворот считается поворотом против часовой стрелки.

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

1 100 1 2 0.01
99 3 8

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

8
2 L