Една
част от опасно пристанище е показана на фигурата, като най-опасните за
корабоплаването зони са защриховани. Както се вижда от фигурата тези
зони са
образувани от пресичането на три прави – всяка със всяка. Три фара,
които
трябва да обезпечат безопасността на плаващите в пристанището кораби са
построени в точките обозначени с черно (пресечните точки на трите
прави).
Задачата е по зададена позиция на кораб в пристанището да се определи
дали
коръбът е:
А) в опасна позиция (т.е. намира се във вътрешността на опасните зони);
Б) в почти-опасна позиция (т.е. намира се по границите на опасните зони, включително местата на фаровете);
В) в безопасна позиция (т.е. нито едно от предходните).
Напишете програма, която решава задачата.
На първия ред на стандартния вход ще бъде зададен броят T на тестовите примери. За всеки тестов пример на един ред ще бъдат зададени координатите X1, Y1, X2, Y2, X3, Y3 на трите фара (взети по посока на часовниковата стрелка) и A,B на кораба. Всички координати са числа с десетична точка в интервала [-100.0,100.0].
За всеки тестов пример програмата трябва да изведе на отделен ред на стандартния изход:
D – ако корабът е в опасна позиция,
A – ако корабът е в почти-опасна позиция
или S – ако корабът е в безопасна позициа.
Пример
|
Вход |
Изход |
3
0. 0. 0. 10. 10. 0. -0.5 –0.5
0. 0. 0. 10. 10. 0. 0. –0.5
0. 0. 0. 10. 10. 0. 1.0 1.5 |
D A S |
Задача C. Празно пространство
Подът на склад е правоъгълник със страни N (5 <= N <= 1000) и M (5 <= M <= 1000) като ъглите му са представени с точките (0, 0), (0, M), (N, 0) и (N, M) в ортогонална координатна състема. Нека K паралелепипедни кутии са поставени в склада (1 <= K <= 70) по такъв начин, че страните им са паралелни на координатните оси. Кутиите може да се припокриват, могат да имат общи страни или части от страни, както и да се допират до стените на склада. Напишете програма C.EXE, която да намери правоъгълник F върху пода на склада с максимално лице, върху който да няма кутии. Правоъгълникът F може да има общи страни или части от страни с кутиите или да се допира до стените на склада.
Данните ще бъдат на стандартния вход. Първият ред ще съдържа цяло положително число T – броят на тестовите примери, които програмата трябва да реши. В първия ред на всеки тестов пример ще бъдат зададени числата N, M и K, разделени с по един интервал. Всеки от следващите K реда на тестовия пример съдържа по четири неотрицателни цели X1, Y1, X2, Y2, pазделени с по един интервал, които описват положението на една кутия – (X1,Y1) са координатите на долния ляв, а (X2, Y2) – на горния десен ъгъл, X1 < X2, Y1 < Y2.
За всеки тестов пример програмата трябва да изведе на стандартния изход лицето на намерения максимален правоъгълник
Пример
Вход
2Изход
96Задача E. Десант
Една десантна група трябвало да проникне във военен обект, който много строго се охранява. Едно от най-големите препятствия били насочените фенери, постовени в точката Р, които осветявали територията около обекта в N (1 <= N < 9) прави линии. Все пак разузнавачите доложили, че зоните, оставащи между тези линии не са осветени. Те доставили и списък на M (1 < M < 99) удобни за прикритие места, като ги номерирали от 1 до М и задали техните координати. С номер 1 означили обекта на нападението. Операцията трябвало да се извърши, така че десантчиците да не пресекат нито една от осветените линии. След продължителното разузнаване оставало само да се напише програма E.EXE, която по дадените данни да открие през кои от местата за прикритие трябва да премине групата, така че да достигне до целта без да пресича осветените линии.
Входните данни се четат от стандартния вход. В първия ред е записано цялото число К – броя на тестовите примери, на следващите редове са записани тестовите примери, организирани по следния начин: на първия ред на всеки тестов пример са записани целите числа N и M, разделени с един интервал. Във втория ред са записани координатите на точката P. В следващите N реда за всяка от осветените прави са записани координатите (разделени с един интервал) на още една точка от правата, различна от P. Останалите M реда на файла съдържат координатите (разделени с един интервал) на поредната от зададените M места за прикритие, в нарастващ ред на номерата им. Всички координати са цели числа между -999 и 999 включително и са относно стандартна координатна система.
На стандартния изход програмата извежда К – по един за всеки тестов пример, всеки от които трябва да съдържа номерата на намерените от програмата обекти за прикритие, разделени с по един интервал. Ако такива не съществуват или ако обекта на нападението лежи върху някоя от дадените прави, тогава програмата трябва да запише 0 в изходния файл.
Пример
Вход
2Изход
2