В равнина са дадени 1000 точки в общо положение (никои три от тях не лежат на една права линия). Да се прекара права, която ги разделя на две групи по 500 точки.
РЕшението може да бъде обяснително, а не строго геометрично построение.
Преглед за печат
В равнина са дадени 1000 точки в общо положение (никои три от тях не лежат на една права линия). Да се прекара права, която ги разделя на две групи по 500 точки.
РЕшението може да бъде обяснително, а не строго геометрично построение.
http://free.hit.bg/dimiters-kv/1000-tochki.jpg
1. Взимаме такава права, при която всички от дадените 1000 точки лежат в едната полуравнина.
(Съществуват безброй такива прави - тия краен брой точки могат да бъдат "оградени" с окръжност и всяка права която не се пресича с окръжноста, ни върши работа за тая първа стъпка)
Тая права я означавам с a.
2. Сега правим "перпендикулярните" проекции на всичките 1000 точки върху тая права a. Тия проекции всъщност са точки върху правата, a броят им е не повече от 1000.
Възможно е проекциите на две точки да съвпадат, но е невъзможно проекциите на повече от две точки да съвпадат, защото в условието е казано, че всеки три точки не лежат на една права.
Означавам ги проекциите "отляво-надясно" с p1, p2, p3 ...pn
Сега е момента да направим и някакво означение на първоначалните 1000 точки, пак "отляво-надясно" с t1, t2, t3...t1000
3. Всяка проекция си има стойност 1 или 2, по отношение на броя на точките които се "проектират" в тая проекция. Тая стойност, ще я означавам със "стойност на проекцията".
4. Сега, почваме да сумираме отляво-надясно "стойностите на проекциите"
5. Ако в сумирането стигнем точно до 500, то чудесно - всяка права която е перпендикулярна на a и е такава, че е "вдясно" след сумата 500, но е преди следващата проекция ни върши работа.
6. (ВИЖ картинката)
В по-екзотичния случай, след сума 499, следва проекция на две точки и следващата сума е 501, съответно т.5 не може да се приложи
6.1. Така както е на картинката, тая проекция на две точки, която е веднага след 499 е означена с pк
Така както е на картинката, двете точки на тая проекция са означени с ts и ts+1 и ts е по-близката точка до правата a.
Така както е на картинката, правата през ts и ts+1 е означена с b
6.2. Избираме произволна точка T лежаща вътре в отсечката tsts+1
6.3. От всички точки ti, които са "вдясно" на правата b (тия точки са краен брой), намираме тая точка tm, при която ъгъл ts+1Ttm e най-малкия.
6.4. И сега, можем да построим права c, такава, че да минава през T и да сключва с правата b такъв ъгъл, който едновременно е по-малък от ъгъл ts+1Ttm и от ъгъл pk-1Ttk
Такава права c ще дели първоначалния брой точки по 500 във всяка полуравнина.
---------------
ПП.
Забелязвате ли, че това решение може леко да се преправи, така че да върши работа и за "по-произволни" 1000 точки, при които го няма ограничението "никои три да не лежат на една права", а се иска единствено "1000 различни точки".
Много добро решение на задачата предлагаш, MitkoS.
Моето е следното:
1. Построявам окръжност к, в която са всичките 1000 точки. Например така: избирам една от точките и сравнявам разстоянията от нея до всички останали. Окръжността има за център избраната точка и радиус, по-голям от разстоянието до най-отдалечената.
2. Избирам права а, която не пресича к.
3. Построявам всичките прави, съединяващи всяка от 1000-те точки с останалите. Всичките или част от тях пресичат а.
4. Върху правата а избирам точка С, която не лежи на никоя от правите от т. 3.
5. Започвам да въртя а около С, например по посока на часовниковата стрелка. Когато правата мине през първата точка, отброявам 1, през втората - 2 и т.н. Като отброя 500 точки, идва номерът с ъгъла...
ПП Изборът на точка С осигурява да не се преброят 2 точки едновременно.
И твоето решение Pitagorvd, става за случая "1000 различни точки" без изискване "никои три да не лежат на една права".
И в двете решения се посочва алгоритъм.
Но така като гледам, при единия алгоритъм изчисленията са от порядък
k1.N
а при другия изчисленията са от порядък
k2.(N^2)
(k1, k2 - фиксирани коефициенти, N-броя на първоначалните точки)
ПП. Казвам "изчисленията", в случай че решим да правим програма някаква
Не разбрах каква е идеята на тази "логическа" задача. Няма никакво практическо приложение, освен ако не пишем 3d програма - пак без практическо значение.