» Главная
eXcode.ru » Статьи » Задачи » Без решений
» Новости
» Опросы
» Файлы
» Журнал



Пользователей: 0
Гостей: 4





Векторы




Задано множество из N двумерных векторов (1 <= N <=500), координаты каждого вектора - целые числа из интеравала [-30000, 30000]. Нулевого вектора в этом множестве нет.
Требуется выделить из этого мнажества подмножество векторов, квадрат модуля суммы которых максимален.

Входные данные содержат N+1 строку. Первая строка содержит значение N, каждая из последующих строк - описание одного вектора: координаты x и y, разделенные одним или несколькими пробелами.

Выходные данные состоят из одной строки, содержащей искомый квадрат модуля суммы векторов.

Пример входных данных

4
1 4
-1 -1
1 -1
-1 4

Пример выходных данных

64
К началу статьи





Добавил: LedWormДата публикации: 2005-09-24 19:48:09
Рейтинг статьи:5.00 [Голосов 1]Кол-во просмотров: 7663

Комментарии читателей

Всего комментариев: 2

2007-06-02 01:11:44
Konst
Среди всех векторов, надо выбрать такие которые бы при суммировании с i-тым вектором(i изменяется от 1 до N), давали бы вектор квадрат длины которого был бы больше чем до суммирования. У тебя получится массив из N элементов, среди которых надо выбрать максимальный (этот шаг можно как-то ускорить, попой чую)
Вот реализация алгоритма на С++:

#include <iostream>
using namespace std;
int main()
{
int N;
cout<<"Input N: ";
cin>>N;
//представляем вектор в виде (a[i];b[i])
double a[N];
double b[N];
cout<<"Input vectors: "<<endl;
for(int i=0;i<N;i++)
{
cin>>a[i]>>b[i];
}
double a_temp[N];
double b_temp[N];
double Res[N];
double t = 0;
for(int j = 0;j<N;j++)
{

a_temp[j]=a[j];
b_temp[j]=b[j];
for(int i = 0;i<N;i++)
{
if(i!=j)//чтоб два раза не прибавить
{
t = a_temp[j]*a[i]+b_temp[j]*b[i];
if(t>0)
{
a_temp[j]+=a[i];
b_temp[j]+=b[i];
}
else if(a[i]*a[i]+b[i]*b[i]>-2*t)
{
a_temp[j]+=a[i];
b_temp[j]+=b[i];
}
}
}
Res[j]=a_temp[j]*a_temp[j]+b_temp[j]*b_temp[j];
}
double Max_res=Res[0];
for(int i =1;i<N;i++)
{
if(Res[i]>Max_res)
Max_res=Res[i];
}
cout<<Max_res<<endl;
system("pause";);
return 0;
}

2006-05-25 22:10:42
Eugene
Как ее делать? Может кто натолкнет на мысль.
Это что, нужно найти вот такую вещь - (x1+x2)*(x1+x2)+(y1+y2)*(y1+y2)?
Ваше имя: *
Текст записи: *
Имя:

Пароль:



Регистрация

Каким способом вы подключены к интернету
Dial-Up
26% (59)
ISDN
1% (2)
Выделенная линия
27% (61)
ADSL
32% (71)
Спутниковый интернет
2% (5)
GPRS-интернет
8% (17)
Другое
4% (9)

Проголосовало: 224
Люблю я струйный принтер. За чернила...
Рейтинг: 5.5/10 (2)
Посмотреть все анекдоты