Обертання дзиґи
Дзиґи є одними з найпопулярніших і найтрадиційніших іграшок. Не лише їх обертання, але й виготовлення власноруч є популярним заняттям.
Один із найпростіших способів зробити дзиґу - це вирізати певну форму з картону і проткнути вісь через її центр мас. Хоча професійно виготовлені дзиґи зазвичай мають тривимірні форми, у цій задачі ми розглядаємо лише двовимірні.
Зазвичай дзиґи мають обертально-симетричні форми, такі як коло, прямокутник (з 2-разовою обертальною симетрією) або правильний трикутник (з 3-разовою симетрією). Хоча такі симетрії корисні для визначення їх центрів мас, вони не є обов'язковими; асиметрична дзиґа також добре обертається, якщо її вісь правильно проткнута в центрі мас.
Коли форма дзиґи задана як шлях для вирізання з картону однакової товщини, ваше завдання - знайти її центр мас, щоб вона добре оберталася. Також, ви повинні визначити, чи знаходиться центр мас на частині вирізаного картону. Якщо ні, ви, звісно, не можете проткнути вісь.
Специфікація для Java: Подані програми на Java не можуть використовувати класи, що реалізують інтерфейс "java.awt.Shape". Ви можете використовувати їх для цілей налагодження.
Вхідні дані
Вхід складається з кількох наборів даних, кожен з яких описує контурний шлях на картоні для вирізання дзиґи. Шлях вказується послідовністю командних рядків, кожен з яких визначає відрізок або дугу.
У наведеному нижче описі команд, поточна позиція - це позиція для початку наступного вирізу, якщо такий є. Після виконання вирізу, зазначеного командою, поточна позиція переміщується в кінцеву позицію зробленого вирізу.
Дані команди є однією з наведених нижче. Назва команди починається з першої колонки рядка, а команда та її аргументи розділяються пробілом. Усі аргументи команд є цілими числами.
start x y
Вказує початкову позицію шляху. Ця команда сама по собі не вказує жодного вирізу; вона лише встановлює поточну позицію як (x, y).
line x y
Вказує лінійний виріз уздовж прямої від поточної позиції до позиції (x, y), яка не є ідентичною поточній позиції.
arc x y r
Вказує круговий виріз уздовж дуги кола. Дуга починається з поточної позиції і закінчується в (x, y), яка не є ідентичною поточній позиції. Дуга має радіус |r|. Коли r негативний, центр кола знаходиться з лівого боку від напрямку цього кругового вирізу; коли він позитивний, він знаходиться з правого боку (Рисунок 1). Абсолютне значення r більше половини відстані між двома кінцями дуги. Серед двох дуг, що з'єднують початкову і кінцеву позиції з заданим радіусом, вказана дуга - це та, у якої центральний кут менше 180 градусів.
close
Закриває шлях, роблячи лінійний виріз до початкової позиції і завершує набір даних. Якщо поточна позиція вже знаходиться в початковій позиції, ця команда просто вказує на кінець набору даних.
Нижче наведено приклад послідовності команд і відповідного шляху. Зверніть увагу, що в цьому випадку заданий радіус −r є негативним, і тому центр дуги знаходиться зліва від дуги. Команда дуги повинна бути інтерпретована, як показано на цьому рисунку, а не навпаки на тому ж колі.
Рисунок 1: Часткова послідовність команд і шлях, вказаний на даний момент
Набір даних починається з команди start і закінчується командою close.
Кінець вводу вказується рядком з командою end.
У наборі даних може бути не більше 100 команд, а у вводу - не більше 100 наборів даних. Абсолютні значення всіх координат і радіусів не перевищують 100.
Ви можете припустити, що шлях не перетинає і не торкається сам себе. Ви також можете припустити, що шляхи ніколи не виходять за межі країв картону, або, іншими словами, картон віртуально нескінченно великий.
Вихідні дані
Для кожного з наборів даних виведіть рядок, що містить x- та y-координати центру мас дзиґи, вирізаної за вказаним шляхом, а потім символ '+' або '-', що вказує, чи знаходиться цей центр на дзиґі, чи ні, відповідно. Дві координати повинні бути у вигляді десяткових дробів. Між двома координатами і між y-координатою і символом '+' або '-' повинен бути пробіл. Інші символи не повинні виводитися. Координати можуть мати похибки менше 10^{−3}. Ви можете припустити, що центр мас знаходиться на відстані не менше 10^{−3} від шляху.
Підказки
Важлива властивість центрів мас полягає в тому, що, коли об'єкт O може бути розкладений на частини O_1, ..., O_n з масами M_1, ..., M_n, центр мас об'єкта O може бути обчислений за формулою:
де G_k - вектор, що вказує на центр мас частини O_k.
Круговий сегмент з радіусом r і кутом θ (в радіанах) має довжину дуги s = rθ і довжину хорди . Його площа A = r^2(θ − sinθ)/2 і його центр мас G знаходиться на відстані y = 2r^3 sin^3(θ/2)/(3A) від центру кола.
Рисунок 2: Круговий сегмент і його центр мас
Рисунок 3: Перша зразкова дзиґа