2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Командный чемпионат мира по программированию. Задача G
Сообщение02.06.2011, 13:56 
Аватара пользователя


21/02/10
1594
Екатеринбург
Прошел очередной командный чемпионат мира по программированию. Наши заняли четвертое место.
http://cm.baylor.edu/scoreboard/

Из списка задач заинтеросавала задача G. Если бы наши ее решили были бы первыми.
http://cm.baylor.edu/digital/icpc2011.pdf

Краткое описание задачи G.
Дано: длины сторон некего многоугольника. S1,S2,...,Sn.
Надо: Вычислить максимальную площадь многоугольника, который можно построить из этих длин сторон.

Пытаюсь ее решить. Возникло несколько математических проблем.

Гипотеза. Многоугольник максимальной площади должен быть вписан в некоторую окружность.

Верна ли эта гипотеза?
Если верна, то возникает вторая проблема вычислить радиус этой окружности.

 Профиль  
                  
 
 Re: Командный чемпионат мира по программированию. Задача G
Сообщение02.06.2011, 14:06 
Заблокирован
Аватара пользователя


17/06/09

2213
Pavlovsky в сообщении #452989 писал(а):
Гипотеза. Многоугольник максимальной площади должен быть вписан в некоторую окружность.

Верна ли эта гипотеза?
Нет. Возьмите 4 стороны по 10 и 2 стороны по 1.

 Профиль  
                  
 
 Re: Командный чемпионат мира по программированию. Задача G
Сообщение02.06.2011, 14:21 
Аватара пользователя


21/02/10
1594
Екатеринбург
И что в этом примере не так? Получится многоугольник очень близкий к квадрату 10х10.

 Профиль  
                  
 
 Re: Командный чемпионат мира по программированию. Задача G
Сообщение02.06.2011, 14:22 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Pavlovsky в сообщении #452989 писал(а):
Надо: Вычислить максимальную площадь многоугольника, который можно построить из этих длин сторон.
Не это надо вычислить.

 Профиль  
                  
 
 Re: Командный чемпионат мира по программированию. Задача G
Сообщение02.06.2011, 14:23 
Заслуженный участник


22/11/10
1183
Гипотеза верна. Порядок сторон - не важен. Радиус окружности от этого не меняется (а вместе с ним и площадь многоугольника).
Доказательство. Используем изопериметрическую задачу.

(Доказательство)

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

 Профиль  
                  
 
 Re: Командный чемпионат мира по программированию. Задача G
Сообщение02.06.2011, 14:35 


24/01/11
207
sup, кстати, радиус вроде можно простым бинпоиском найти

 Профиль  
                  
 
 Re: Командный чемпионат мира по программированию. Задача G
Сообщение02.06.2011, 14:44 
Заслуженный участник


22/11/10
1183
Ну конечно. А еще и метод Ньютона существует.

 Профиль  
                  
 
 Re: Командный чемпионат мира по программированию. Задача G
Сообщение02.06.2011, 14:47 
Аватара пользователя


21/02/10
1594
Екатеринбург
Sup ты гений. На подобных соревнованях обычно берут в команду двух программистов и одного математика. Наш математик явно подкачал.
Пытаюсь решить скучную задачу с синусами. Получилось так:
\sum_{i=1}^{n}{\arcsin(\frac {S_i} {2R})}=\pi

Если arcsin разложить в ряд тэйлора (взять два первых члена), то получится кубическое уранение. Но вот хватит ли только двух членов? По условиям задачи точность должна быть 10^-4

-- Чт июн 02, 2011 16:49:36 --

Equinoxe в сообщении #453001 писал(а):
радиус вроде можно простым бинпоиском найти

sup в сообщении #453005 писал(а):
А еще и метод Ньютона существует


Не знаю какой лимит времени был у этой задачи. Боюсь что приближенные алгоритмы вычисления могут в этот лимит не войти.

 Профиль  
                  
 
 Re: Командный чемпионат мира по программированию. Задача G
Сообщение02.06.2011, 14:55 
Заблокирован
Аватара пользователя


17/06/09

2213
Это как раз что-то вроде симплекс-метода. Геометрическая интерпретация симплекс-метода и есть поиск многоугольника максимальной площади. Только немножко надо модернизировать.

 Профиль  
                  
 
 Re: Командный чемпионат мира по программированию. Задача G
Сообщение02.06.2011, 14:55 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Pavlovsky в сообщении #453007 писал(а):
Пытаюсь решить скучную задачу с синусами. Получилось так:
\sum_{i=1}^{n}{\arcsin(\frac {S_i} {2R})}=\pi

Неверная формула. Справа не обязательно $\pi$

 Профиль  
                  
 
 Re: Командный чемпионат мира по программированию. Задача G
Сообщение02.06.2011, 14:59 
Аватара пользователя


21/02/10
1594
Екатеринбург
TOTAL в сообщении #453012 писал(а):
Неверная формула. Справа не обязательно

Ах да вспомнил. Центр окружности не обязательно может находиться внутри многоугольника.

 Профиль  
                  
 
 Re: Командный чемпионат мира по программированию. Задача G
Сообщение02.06.2011, 15:01 
Заблокирован
Аватара пользователя


17/06/09

2213
Pavlovsky в сообщении #452996 писал(а):
И что в этом примере не так? Получится многоугольник очень близкий к квадрату 10х10.
Очевидно, но в одной из вершин там будет такая загагулинка из сторонок по $1$. Её вы не впишите ни в одну окружность, т.к. многоугольник будет невыпуклый.

 Профиль  
                  
 
 Re: Командный чемпионат мира по программированию. Задача G
Сообщение02.06.2011, 15:04 
Аватара пользователя


21/02/10
1594
Екатеринбург
age в сообщении #453018 писал(а):
Очевидно, но в одной из вершин там будет такая загагулинка из сторонок по . Её вы не впишите ни в одну окружность, т.к. многоугольник будет невыпуклый.


Вы очень ошибаетесь. Легко доказать что многоугольник с максимальной площадью - выпуклый.

 Профиль  
                  
 
 Re: Командный чемпионат мира по программированию. Задача G
Сообщение02.06.2011, 15:08 
Заблокирован
Аватара пользователя


17/06/09

2213
Хотя нет, Вы, Equinoxe и sup правы. Его стороны по 1 можно прибавить к двум сторонам по 10, тогда получится выпуклый четырёхугольник со сторонами $10,10,11,11$. Если так можно?

 Профиль  
                  
 
 Re: Командный чемпионат мира по программированию. Задача G
Сообщение02.06.2011, 15:34 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
Слушайте, ну ведь 10 сообщений назад sup уже доказал, что максимальный многоугольник - вписанный.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 21 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group