Технический форум
Вернуться   Технический форум > Программирование > Форум программистов > Помощь студентам


Ответ
 
Опции темы Опции просмотра
Старый 30.11.2013, 18:49   #1 (permalink)
Pender
Новичок
 
Регистрация: 30.11.2013
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
По умолчанию Олимпиадная задача Angry Birds

Здесь условие задачи http ://acm.timus.ru/problem.aspx?space=1&num=1875

Не могу написать программу.
Математическое решение выглядит как-то так:
считаем коэффициенты квадратного уравнения a и b для всех возможных пар точек:
a = (y1x2 - y2x1) /( x1x2(x1-x2) )
b = (y1-y2) / (x1-x2) - a(x1+x2)
и тогда, если выполняется условие (a<0&&b!=0) получаем две точки, лежащие на одной параболе.
Затем проверяем не лежит ли третья точка на этой параболе
y3x1x2(x1-x2) = (y1x2 - y2x1) x32 + (y2x12 - y1x22) x3
ну и так для всех точек.
Я что-то упускаю и уже несколько дней ничего не могу придумать. Написал кое-что, но даже показывать стыдно. Разумеется не работает, что не удивительно.
Код:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define N 5

bool Pass (int a, int b, int c);
bool func (int i, int j);
struct point { 
              int x;
              int y;
             };
int main()
{
int i,j,k,bird=5;
 
  struct point P[N];
  FILE* input = fopen ("input.txt", "r");
  if (!input) {
     printf ("Can not open file");
     return 0;
    }
  for (i = 0; i<N; i++)
    {
     fscanf (input, "%d%d", &P[i].x, &P[i].y);
     printf ("x= %d  y= %d\n",P[i].x, P[i].y);
    }
  fclose (input);
  for (i = 0; i<N; i++)
    {
     for (j = i+1; j<N; j++)
       {
        if (func(i,j))
         {
          bird = 4;
          for (k = j+1; k<N; k++)
            {
              if (Pass(i, j, k))
                bird--;
            }
        }
       }
    }
printf("bird = %d",bird);
  getch();
  return 0;
 }

bool func (int i, int j)
 {
  struct point P[N];
  double a = (P[i].y*P[j].x-P[j].y*P[i].x)  / (P[i].x*P[j].x*(P[i].x-P[j].x));
  double b = (P[i].y-P[j].y)/(P[i].x-P[j].x)-a*(P[i].x+P[j].x);
  printf("a= %f, b= %f\n",a,b);
  return (a<0 && b!=0);
 }
bool Pass(int a, int b, int c)
 {

  struct point P[N]; 
  return (P[a].x * P[a].x) * P[b].x * P[c].y +
        P[a].x * P[b].y * (P[c].x * P[c].x) +
        P[a].y * (P[b].x * P[b].x) * P[c].x -
        (P[a].x * P[a].x) * P[b].y * P[c].x -
        P[a].x * (P[b].x * P[b].x) * P[c].y -
        P[a].y * P[b].x * (P[c].x * P[c].x) == 0;
 }
Pender вне форума   Ответить с цитированием

Старый 30.11.2013, 18:49
Helpmaster
Member
 
Аватар для Helpmaster
 
Регистрация: 08.03.2016
Сообщений: 0

Наверняка тут вы найдете что то полезное, по этому дам вам ссылки на похожи темы

Angry Bot FREE - головоломка про злого робота
Angry Birds Star Wars - возвращение злых птичек
Bad Piggies - свиньи из Angry Birds возвращаются
Angry Birds Star Wars – птицы-джедаи
Angry Birds Space – злые птички в космосе
Angry Birds Seasons - продолжение злых птиц

Старый 30.11.2013, 18:56   #2 (permalink)
Николай_С
Радиоинженер
 
Аватар для Николай_С
 
Регистрация: 25.09.2012
Адрес: г.Дзержинск Нижегородской обл.
Сообщений: 25,273
Записей в дневнике: 7
Сказал(а) спасибо: 291
Поблагодарили 219 раз(а) в 70 сообщениях
Репутация: 110185
По умолчанию

А Вы ничего не попутали?
По ссылке открываются злые птички.
Николай_С вне форума   Ответить с цитированием
Старый 30.11.2013, 19:00   #3 (permalink)
Pender
Новичок
 
Регистрация: 30.11.2013
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
По умолчанию

Нет, а что Вас смущает? )
Pender вне форума   Ответить с цитированием
Старый 30.11.2013, 19:02   #4 (permalink)
Daniellos
Хозяин Медной Горы
 
Аватар для Daniellos
 
Регистрация: 01.08.2011
Адрес: Армавир
Сообщений: 12,159
Записей в дневнике: 8
Сказал(а) спасибо: 751
Поблагодарили 88 раз(а) в 27 сообщениях
Репутация: 57416
По умолчанию

Сложно было выложить условие?

Цитата:
Игра выглядит следующим образом. В левом нижнем углу карты находится рогатка, стреляющая злыми птичками. Она может запустить птичку с любой скоростью под любым углом к поверхности земли. Цель игры — поразить птичками обезьянок, висящих в воздухе справа от рогатки. В игре на птичку не действуют никакие силы, кроме силы тяжести, придающей ей ускорение g = 9.81 м/с2 , направленное вниз. Из-за этого горизонтальная составляющая скорости птички постоянна, а вертикальная изменяется со временем.
В уровне, который никак не могут пройти наши программисты, есть рогатка, пять обезьянок и больше ничего. Требуется уничтожить всех обезьянок минимальным количеством выстрелов. Столкновение с обезьянкой никак не вредит птичке, и она продолжает двигаться так же, как до столкновения. Птички и обезьянки настолько малы, что их можно считать точками. Карта уровня бесконечна вправо и вверх.
Daniellos вне форума   Ответить с цитированием
Старый 30.11.2013, 19:07   #5 (permalink)
Pender
Новичок
 
Регистрация: 30.11.2013
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
По умолчанию

Это не полное условие.
Цитата:
Игра выглядит следующим образом. В левом нижнем углу карты находится рогатка, стреляющая злыми птичками. Она может запустить птичку с любой скоростью под любым углом к поверхности земли. Цель игры — поразить птичками обезьянок, висящих в воздухе справа от рогатки. В игре на птичку не действуют никакие силы, кроме силы тяжести, придающей ей ускорение g = 9.81 м/с2 , направленное вниз. Из-за этого горизонтальная составляющая скорости птички постоянна, а вертикальная изменяется со временем.
В уровне, который никак не могут пройти наши программисты, есть рогатка, пять обезьянок и больше ничего. Требуется уничтожить всех обезьянок минимальным количеством выстрелов. Столкновение с обезьянкой никак не вредит птичке, и она продолжает двигаться так же, как до столкновения. Птички и обезьянки настолько малы, что их можно считать точками. Карта уровня бесконечна вправо и вверх.
Исходные данные
В каждой из пяти строк входа находится пара целых положительных чисел, не превосходящих 10 000 — координаты очередной обезьянки в метрах. Рогатка находится в точке (0, 0), ось Ox направлена вправо, ось Oy — вверх. Гарантируется, что не существует прямой, содержащей рогатку и более одной обезьянки.
Результат
Выведите минимальное число выстрелов, необходимое для того, чтобы поразить всех обезьянок.
Pender вне форума   Ответить с цитированием
Ads

Яндекс

Member
 
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
Старый 30.11.2013, 19:16   #6 (permalink)
Николай_С
Радиоинженер
 
Аватар для Николай_С
 
Регистрация: 25.09.2012
Адрес: г.Дзержинск Нижегородской обл.
Сообщений: 25,273
Записей в дневнике: 7
Сказал(а) спасибо: 291
Поблагодарили 219 раз(а) в 70 сообщениях
Репутация: 110185
По умолчанию

Это я и без компьютера скажу - при условии:
Цитата:
Гарантируется, что не существует прямой, содержащей рогатку и более одной обезьянки.
д.б. 5 выстрелов.
Николай_С вне форума   Ответить с цитированием
Старый 30.11.2013, 19:18   #7 (permalink)
Pender
Новичок
 
Регистрация: 30.11.2013
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
По умолчанию

Птица летит по параболе, а значит нужно просто посчитать наименьшее кол-во этих парабол, образованных заданными точками.
5 птичек будет только в том случает, если ни одна пара точек не лежит на одной параболе =)
Pender вне форума   Ответить с цитированием
Старый 30.11.2013, 19:28   #8 (permalink)
Vladimir_S
Специалист
 
Регистрация: 27.08.2008
Адрес: Санкт-Петербург
Сообщений: 27,807
Сказал(а) спасибо: 340
Поблагодарили 583 раз(а) в 208 сообщениях
Репутация: 113184
По умолчанию

К сожалению, в СИ я не программирую, но общий ход решения, мне кажется, Вы нашли верно. На всякий случай: если α - угол выстрела по отношению к горизонту, а v0 - начальная скорость, то уравнение траектории птички должно выглядеть так (надеюсь, не наврал):
y = x*tg(α)-(g*x²)/(2*(v0)²*cos²(α))
Остаётся выразить α и v0 через x и y, а затем, подставляя все возможные комбинации пар (их 10 штук) найти "кратные" выстрелы, причем включая возможность поражения одним выстрелом не только двух, но и трёх, четырех и даже всех пяти обезьянок. Соответственно, если таковые найдутся, то на их количество следует уменьшить исходное значение (5 выстрелов).
Как-то так.
Vladimir_S вне форума   Ответить с цитированием
Ads

Яндекс

Member
 
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
Ответ

Опции темы
Опции просмотра

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Выкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.




Часовой пояс GMT +4, время: 15:11.

Powered by vBulletin® Version 6.2.5.
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.