30.11.2013, 18:49 | #1 (permalink) |
Новичок
Регистрация: 30.11.2013
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
|
Олимпиадная задача Angry Birds
Не могу написать программу. Математическое решение выглядит как-то так: считаем коэффициенты квадратного уравнения 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:49 | |
Helpmaster
Member
Регистрация: 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,301
Записей в дневнике: 7
Сказал(а) спасибо: 292
Поблагодарили 219 раз(а) в 70 сообщениях
Репутация: 110185
|
А Вы ничего не попутали?
По ссылке открываются злые птички. |
30.11.2013, 19:02 | #4 (permalink) | |
Хозяин Медной Горы
Регистрация: 01.08.2011
Адрес: Армавир
Сообщений: 12,159
Записей в дневнике: 8
Сказал(а) спасибо: 751
Поблагодарили 88 раз(а) в 27 сообщениях
Репутация: 57416
|
Сложно было выложить условие?
Цитата:
|
|
30.11.2013, 19:07 | #5 (permalink) | |
Новичок
Регистрация: 30.11.2013
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
|
Это не полное условие.
Цитата:
|
|
Ads | |
Member
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
|
30.11.2013, 19:16 | #6 (permalink) | |
Радиоинженер
Регистрация: 25.09.2012
Адрес: г.Дзержинск Нижегородской обл.
Сообщений: 25,301
Записей в дневнике: 7
Сказал(а) спасибо: 292
Поблагодарили 219 раз(а) в 70 сообщениях
Репутация: 110185
|
Это я и без компьютера скажу - при условии:
Цитата:
|
|
30.11.2013, 19:18 | #7 (permalink) |
Новичок
Регистрация: 30.11.2013
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
|
Птица летит по параболе, а значит нужно просто посчитать наименьшее кол-во этих парабол, образованных заданными точками.
5 птичек будет только в том случает, если ни одна пара точек не лежит на одной параболе =) |
30.11.2013, 19:28 | #8 (permalink) |
Специалист
Регистрация: 27.08.2008
Адрес: Санкт-Петербург
Сообщений: 27,807
Сказал(а) спасибо: 340
Поблагодарили 583 раз(а) в 208 сообщениях
Репутация: 113184
|
К сожалению, в СИ я не программирую, но общий ход решения, мне кажется, Вы нашли верно. На всякий случай: если α - угол выстрела по отношению к горизонту, а v0 - начальная скорость, то уравнение траектории птички должно выглядеть так (надеюсь, не наврал):
y = x*tg(α)-(g*x²)/(2*(v0)²*cos²(α)) Остаётся выразить α и v0 через x и y, а затем, подставляя все возможные комбинации пар (их 10 штук) найти "кратные" выстрелы, причем включая возможность поражения одним выстрелом не только двух, но и трёх, четырех и даже всех пяти обезьянок. Соответственно, если таковые найдутся, то на их количество следует уменьшить исходное значение (5 выстрелов). Как-то так. |
Ads | |
Member
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
|
|
|