Спорная территория имела форму выпуклого многоугольника. Два государства, воевавшие за...

0 голосов
108 просмотров

Спорная территория имела форму выпуклого многоугольника. Два государства, воевавшие за нее, утомившись длительным противостоянием, решили заключить мирный договор,согласно которому спорная территория должна быть поделена между ними в соотношении, в соответствии с оставшейся численностью войск этих государств. Для простоты было решено провести границу в виде вертикального отрезка. Определите, где именно следует установить границу смотрите фото p.s. задание должно быть в паскаль и полным то есть начиная с var до end.


image

Информатика (28 баллов) | 108 просмотров
0

ну, ну...

0

Задача решается двоичным поиском, но решение слишком муторное, напрягаться лень.

0

Двоичный поиск не решает эту задачу. Он работает в упорядоченном наборе дискретных значений. Здесь скорее что-то вроде поиска решения медом дихотомии, но тогда нужно задавать точность решения. Ответ в примере 3.000 демонстрирует, что решение не обязано быть целочисленным. Вот это - главная муть.

0

Двоичный поиск решает проблему. Находите площадь многоугольника. Находите площадь правого многоугольника Q. Затем двоичным поиском находите площадь правого многоугольника с точностью до 3 знаков после запятой. При этом надо будет каждый раз находить 2 стороны, которые пересекает прямая, формировать новый многоугольник справа и вычислять его площадь.

0

Вы серьезно не отличаете двоичный поиск от метода деления отрезка пополам?

0

И второе. Это в примере даны три десятичных знака. А в задании не указано, что их должно быть именно три. Это автор задачи должен определить, какая ему точность нужна, потому что вводить ее нельзя по условию задачи.

0

Когда левая и правая границы поиска будут отличаться менее, чем на 0,001, поиск можно прекратить. Когда область решения разбивается на две половины, это и есть двоичный поиск - для простого народа.

0

Еще раз, поиск - это нахождение (или не нахождение) одного из элементов существующей последовательности, который удовлетворяет условию поиска.

0

А я не грамотный. Академиев не кончали.

Дан 1 ответ
0 голосов

Решение в прикрепленном файле.

Ввод - вывод

8 4 1

-3.5 1

-2.5 -1

-0.5 -2

2 -1

3 1

3.5 3

1 3

-2 2

1.729



Скачать вложение Текст (TXT)
(9.7k баллов)