Технический форум

Технический форум (http://www.tehnari.ru/)
-   Помощь студентам (http://www.tehnari.ru/f41/)
-   -   Олимпиадная задача Angry Birds (http://www.tehnari.ru/f41/t92730/)

Pender 30.11.2013 18:49

Олимпиадная задача 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;
 }


Николай_С 30.11.2013 18:56

А Вы ничего не попутали?
По ссылке открываются злые птички. ;)

Pender 30.11.2013 19:00

Нет, а что Вас смущает? )

Daniellos 30.11.2013 19:02

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

Цитата:

Игра выглядит следующим образом. В левом нижнем углу карты находится рогатка, стреляющая злыми птичками. Она может запустить птичку с любой скоростью под любым углом к поверхности земли. Цель игры — поразить птичками обезьянок, висящих в воздухе справа от рогатки. В игре на птичку не действуют никакие силы, кроме силы тяжести, придающей ей ускорение g = 9.81 м/с2 , направленное вниз. Из-за этого горизонтальная составляющая скорости птички постоянна, а вертикальная изменяется со временем.
В уровне, который никак не могут пройти наши программисты, есть рогатка, пять обезьянок и больше ничего. Требуется уничтожить всех обезьянок минимальным количеством выстрелов. Столкновение с обезьянкой никак не вредит птичке, и она продолжает двигаться так же, как до столкновения. Птички и обезьянки настолько малы, что их можно считать точками. Карта уровня бесконечна вправо и вверх.

Pender 30.11.2013 19:07

Это не полное условие.
Цитата:

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

Николай_С 30.11.2013 19:16

Это я и без компьютера скажу - при условии:
Цитата:

Гарантируется, что не существует прямой, содержащей рогатку и более одной обезьянки.
д.б. 5 выстрелов. :)

Pender 30.11.2013 19:18

Птица летит по параболе, а значит нужно просто посчитать наименьшее кол-во этих парабол, образованных заданными точками.
5 птичек будет только в том случает, если ни одна пара точек не лежит на одной параболе =)

Vladimir_S 30.11.2013 19:28

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


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

Powered by vBulletin® Version 4.5.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.