XIV конкурс по програмиране на PC Magazine Bulgaria и Мусала Софт

Стартира 1-ви кръг на конкурса по програмиране на PC Magazine Bulgaria и Мусала Софт
В този брой на сп. PC Magazine Bulgaria стартира четиринадесетото издание на най-елитния частен конкурс по програмиране в страната, организиран съвместно от списанието и фирма Мусала Софт. Задачите в кръговете ще продължат да са от алгоритмичен и практико-приложен характер, като същевременно сме се постарали да предложим приятни изненади на състезателите и да им осигурим все по-вълнуващи награди.

Гама лъчи
Мечо Пух не се задоволи с обикновените лазерчета, с които играеха заедно с Йори още като деца. Сега Мечо Пух се е насочил към малко по-необичайно за своята възраст занимание, а именно – контролирано излъчване на гама-лъчи в хомогенно наситени акациеви медени пари. Експерименталната установка на Мечо Пух представлява множество от N еднакви радиоактивни източника, всеки от които е поставен в точка Si и чието праволинейно лъчение е насочено по посока на точка Ei (1<=i<=N), където гама- лъчът се поглъща изцяло от бурканче с мед, повишавайки вкусовите свойства на меда. Всеки източник поражда поле с постоянен потенциал Fi(d)=Fi0*e^(-mu*d) в точка X на разстояние d от източника. Mu представлява константен параметър на парата, а Fi0 е константа, характерна за източниците. Следвайки принципа на суперпозицията, потенциалът в точка се равнява на сумата на потенциалите в тази точка в полетата, породени от различните източници. Проблеми с експериментите не са добре дошли и затова той трябва да е наясно с „опасните“ точки в опитната установка, т.е. такива, при които се пресичат два лъча и потенциалът достига определен максимум FiMax.

На първия ред на входния файл gammarays.in са записани съответно естественото число N (N<=10^6) и реалните числа mu, Fi0, FiMax (0<=2*Fi0<=2, 0<=mu<=1), зададени с не повече от 6 знака след десетичната запетая и разделени с интервали. Всеки от следващите N реда съдържа по шест числа в интервала [0;100] - съответно xyz координатите на поредния източник и xyz координатите на съответното бурканче мед.

На първия ред на изходния файл gammarays.out изведете броя на опасните точки M. На всеки от следващите M реда изведете тройка числа, разделени с интервал, описващи една опасна точка както следва: номерата на двата източника (започвайки номерирането от 1 и съответстващо на реда на източниците във входните данни), съставящи потенциала в съответната опасна точка, последвани от потенциала в точката с абсолютна грешка, не по-голяма от 10^-4.

Бурканчетата мед и източниците са достатъчно малки, за да не предизвикват изменения в анализирането на гама-лъчите.

За точките върху източника и бурканчетата също е дефиниран потенциалът на полето, породен от лъчите. Вследствие на това те също биха могли да бъдат опасни точки.

Приема се стойност на Неперовото число: e=2,718281828459.

Пресечните точки на проекциите на лъчите във всяка от трите проекционни равнини (пренебрегвайки всяка една от координатите) ще са не повече от 10^6.

Няма три лъча, проекциите на които да се пресичат в една точка, защото това би довело до унищожаване на всичкия мед и антимед в неговата и околните гори.

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

Всеки два лъча имат не повече от една обща точка.

Два лъча се пресичат, ако разстоянието между тях е не по-голямо от 10^-4.

Примерен вход: 4 0.3 1.0 1.1 0 2 1 5 2 1 1 1 0 3 3 2 4 0 2 4 4 0 0 4 7.8 5 0 3.1

Примерен изход: 11 2 1.1435

Коментар:
Лъчите 1 и 2 се пресичат в точка (2, 2, 1) със сумарен потенциал 1.1435.
Лъчите 1 и 3 се пресичат в точка (4, 2, 1) със сумарен потенциал 0.8124.

Тъй като FiMax>0.8124, опасна е само пресечната точка на първите два лъча.

Решенията на задачата може да изпратите чрез системата за upload директно на сайта http://konkurs.musala.com до 11 ноември 2008 г.