Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
#1

Найти минимальный путь на земельном участке вдоль ограждения - C++

13.04.2013, 16:04. Просмотров 497. Ответов 10
Метки нет (Все метки)

Земельный участок является прямоугольником со сторонами А и В. На границе заданы точки 1 и 2 с координатами (X1; Y1) и (X2; Y2) соответственно. Какой минимальной длины тропа соединяет точки 1 и 2. Тропа может проходить только по краю. Размеры участка и координаты точек - целые числа, лежащие в пределах от 0 до 1000.
Входные данные: числа A, B, X1, Y1, X2, Y2.
Выходные данные: единственное число - меньшая длина ограждения
Пример:
I: 6 4 3 4 6 2
O: 5

Как решить эту задачу?
Изображения
 
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.04.2013, 16:04     Найти минимальный путь на земельном участке вдоль ограждения
Посмотрите здесь:

Задача про минимальный путь в лабиринте. - C++
Вот собственно сама задача: Разработать программу, которая ищет минимальный путь в лабиринте. Лабиринт представляет собой матрицу...

Минимальный путь между двух точек - C++
Здравствуйте! Я бы хотел сделать простенькую программу, которая бы находила минимальный путь между двух точек. Сделал я пока что-то такое...

Минимальный путь из левой верхней в правую нижнюю клетку таблицы. - C++
Не могу понять в чем ошибка...помогите. Химическая тревога (Время: 1 сек. Память: 16 Мб Сложность: 50%) Произошло радиоактивное...

Строительство на участке земли - C++
Многоуважаемые сенсеи и профессионалы матан, если есть возможность поделитесь мыслями по поводу решения данной задачи, буду премного...

Найти путь к файлу - C++
ОБХОД ГРАФА В ШИРИНУ Задание: Требуется найти путь к файлу, указанному в первой строке входного файла. Структура каталогов задана...

Протабулировать функцию на участке a до b с шагом h - C++
Нуждаюсь в вашей помощи! Протабулировать функцию на участке a до b с шагом h.

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zer0mail
2330 / 1956 / 192
Регистрация: 03.07.2012
Сообщений: 7,013
Записей в блоге: 1
13.04.2013, 17:50     Найти минимальный путь на земельном участке вдоль ограждения #2
Примитивная задача, неинтересно обсуждать. Берешь верхнюю левую точку и идешь по часовой.
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
13.04.2013, 18:00  [ТС]     Найти минимальный путь на земельном участке вдоль ограждения #3
Цитата Сообщение от zer0mail Посмотреть сообщение
Примитивная задача, неинтересно обсуждать. Берешь верхнюю левую точку и идешь по часовой.
Мое решение:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <math.h>
 
using namespace std;
 
int main(void)
{
    int a, b, x1, y1, x2, y2;
    cin>>a>>b>>x1>>y1>>x2>>y2;
    int p, s;
    p = (a + b) * 2;
    s = fabs(x2 - x1) + fabs(y2 - y1);
    if (s > p / 2) s = p - s;
    cout<<s;
    return 0;
}
Ошибка на 9 тесте.
zer0mail
2330 / 1956 / 192
Регистрация: 03.07.2012
Сообщений: 7,013
Записей в блоге: 1
13.04.2013, 18:07     Найти минимальный путь на земельном участке вдоль ограждения #4
Возьми точки на середине верхней и нижней грани и посмотри свое решение.
Блин, тут всего три варианта взаиморасположения точек и то заблудился...
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
13.04.2013, 18:24  [ТС]     Найти минимальный путь на земельном участке вдоль ограждения #5
Да, неверно считает... Можешь написать алгоритм?
yekka
385 / 149 / 8
Регистрация: 12.05.2011
Сообщений: 450
13.04.2013, 18:25     Найти минимальный путь на земельном участке вдоль ограждения #6
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <cstdlib>
#include <iostream>
 
int main() {
    int a, b, x1, y1, x2, y2;
    std::cin >> a >> b >> x1 >> y1 >> x2 >> y2;
 
    int hp = (a + b);
 
    int path1, path2, result;
    path1 = x1 + y1;
    path2 = x2 + y2;
 
    if ((b * x1 - a * y1) * (b * x2 - a * y2) > 0) {
        result = std::abs(path1 - path2);
    } else {
        result = path1 + path2;
    }
 
    if (result > hp) {
        result = 2 * hp - result;
    }
 
    std::cout << result << std::endl;
}
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
13.04.2013, 18:38  [ТС]     Найти минимальный путь на земельном участке вдоль ограждения #7
yekka, ошибка на 11 тесте
yekka
385 / 149 / 8
Регистрация: 12.05.2011
Сообщений: 450
13.04.2013, 18:59     Найти минимальный путь на земельном участке вдоль ограждения #8
действительно, слегка поторопился

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <cstdlib>
#include <iostream>
 
int main() {
    int a, b, x1, y1, x2, y2;
    std::cin >> a >> b >> x1 >> y1 >> x2 >> y2;
 
    int hp = (a + b);
 
    int path1, path2, result;
    path1 = x1 + y1;
    path2 = x2 + y2;
 
    if ((b * x1 - a * y1) * (b * x2 - a * y2) >= 0) {
        result = std::abs(path1 - path2);
    } else {
        result = path1 + path2;
    }
 
    if (result > hp) {
        result = 2 * hp - result;
    }
 
    std::cout << result << std::endl;
}
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
13.04.2013, 19:08  [ТС]     Найти минимальный путь на земельном участке вдоль ограждения #9
Так же, не прошло решение.
yekka
385 / 149 / 8
Регистрация: 12.05.2011
Сообщений: 450
13.04.2013, 19:40     Найти минимальный путь на земельном участке вдоль ограждения #10
это переполнение
попробуй заменить инты на long long во всех трех местах
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.04.2013, 19:46     Найти минимальный путь на земельном участке вдоль ограждения
Еще ссылки по теме:

Найти максимальный путь в графе - C++
Аллаху акбар, парни. есть задача, необходимо построить такой многоугольник(не обязательно выпуклый) с вершинами в заданном на плоскости...

Что происходит в этом участке кода? - C++
Что это и как называется ? int * (* tArr2);

Найти кратчайший путь шахматного короля - C++
Здравствуйте, имеется задача: Есть шахматное поле NxM N, M ≤ 10^9 На шахматном поле отмечено два прямоугольника размерами не менее...

Как найти кратчайший путь в лабиринте? - C++
Чтобы найти кратчайший путь в лабиринте использую волновой алгоритм, его сделал, но вот кратчайший путь не получается восстановить. ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
A1exSun
C#
55 / 55 / 1
Регистрация: 09.03.2013
Сообщений: 214
13.04.2013, 19:46  [ТС]     Найти минимальный путь на земельном участке вдоль ограждения #11
Точно. Прошло все тесты. Спасибо!
Yandex
Объявления
13.04.2013, 19:46     Найти минимальный путь на земельном участке вдоль ограждения
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru