Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

(С++)Вычисление минимальной проекции выпуклого многоугольника

19K
24 октября 2007 года
Paradoxek
45 / / 24.10.2007
С++
на плоскости х-у координатами вершин задан выпуклый многоугольник. Определить велечину его минимальной проекции на одну из осей.Программа должна читать данные из файла INPUT.TXT, содержащего: в первой строке-число вершин многоугольника N(2<N<100); в следующих N строках - по два вещественных числа - координаты х и у вершин (0<=x и у<=100). Программа должна вывести в фаил OUTPUT.TXT велечину минимальной проекции многоугольника на ось, вычесленную с точностью до 3-го знака после десятичной точки.


и плииз подскажите чё такое минимальная проекция, чем отличается от обычной проекции?

[COLOR="Red"]В названии темы надо указывать язык программирования.[/COLOR]модератор
Страницы:
13K
26 ноября 2007 года
specter
113 / / 28.09.2007
Цитата: cheburator
Вполне возможно.
Меня вот что интересует. Ты говорил, что мое утверждение полностью верное. Ты где-то нашел доказательство?


Нет, я доказательство не искал... просто на сколько я помню, то данная задача рассматривалась в курсе вышки ;)

Цитата: cheburator
Вполне возможно.
И насчет того, что для невыпуклого можно взять разность между max-min


На счет минимума и максимума - это предположение. Если хочешь могу объяснить почему я считаю, что это будет работать :)

19K
26 ноября 2007 года
Paradoxek
45 / / 24.10.2007
Цитата: specter
Юзай Visual C++



дайте ссылочку плиз где скачать?

13K
26 ноября 2007 года
specter
113 / / 28.09.2007
Цитата: Paradoxek
дайте ссылочку плиз где скачать?


А ты сможешь 2 гига вытянуть? ;) Лучше диск возьми у кого-нить или купи... проще будет. Называется Visual Studio 2005 (есть еще Visual Studio .net 2003).

320
26 ноября 2007 года
m_Valery
1.0K / / 08.01.2007
Paradoxek,получаешь предупреждение.Ты чего тут рассуждаешь не по теме ? Хочешь рассуждать - в Гостевую или Отдохнем !
19K
26 ноября 2007 года
Paradoxek
45 / / 24.10.2007
выдает:
Loaded 'ntdll.dll', no matching symbolic information found.
Loaded 'C:\WINDOWS.XP2\system32\kernel32.dll', no matching symbolic information found.
The thread 0x974 has exited with code 0 (0x0).
The program 'C:\Documents and Settings\Вади\Мои документы\Debug\Cpp1.exe' has exited with code 0 (0x0).

запускается и сразу вылетает
13K
27 ноября 2007 года
specter
113 / / 28.09.2007
Цитата: Paradoxek
выдает:
Loaded 'ntdll.dll', no matching symbolic information found.
Loaded 'C:\WINDOWS.XP2\system32\kernel32.dll', no matching symbolic information found.
The thread 0x974 has exited with code 0 (0x0).
The program 'C:\Documents and Settings\Вади\Мои документы\Debug\Cpp1.exe' has exited with code 0 (0x0).

запускается и сразу вылетает


а ты создал в папке с программой файл input.txt с параметрами? Если это файл не найдет программа завершает свою работу
если прога отработает нормально, то ты увидишь что-то типа "Нажмите любую клавишу для продолжения..."

19K
27 ноября 2007 года
Paradoxek
45 / / 24.10.2007
ну вот допустим дан шестиугольник
a(4;6)
b(6;3.5)
c(6;2.5)
d(3;2)
e(2;1)
f(1.5;3)
разве его минимальная проекция будет равна 0???
350
28 ноября 2007 года
cheburator
589 / / 01.06.2006
Как у тебя получилось 0?
У меня получилось 14.75 / sqrt(15.25) - примерно 3.78.
Если ты взял алгоритм для выпуклого многоугольника, естественно, он может дать неверный результат, поскольку твой шестиугольник - невыпуклый.
19K
28 ноября 2007 года
Paradoxek
45 / / 24.10.2007
ну я использовал код который написал specter
13K
28 ноября 2007 года
specter
113 / / 28.09.2007
Цитата: Paradoxek
ну вот допустим дан шестиугольник
a(4;6)
b(6;3.5)
c(6;2.5)
d(3;2)
e(2;1)
f(1.5;3)
разве его минимальная проекция будет равна 0???


Не дочитал, что координаты вещественные ;) Вот тебе маленький фикс:

Код:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct Point
{
    float x;
    float y;
};

double findDistance(Point &point, Point &edgePoint1, Point &edgePoint2)
{
    double a = edgePoint2.y-edgePoint1.y;
    double b = edgePoint1.x-edgePoint2.x;
    double c = edgePoint2.x*edgePoint1.y - edgePoint1.x*edgePoint2.y;

    return abs (point.x*a + point.y*b + c) / sqrt (a*a + b*b);
}

void main()
{
    FILE *f;
    f = fopen("input.txt", "rb");
    if (!f)
        return;

    Point points[101];
    int N;

    //чтение из файла
    fscanf(f, "%d\n", &N);
    int i, j;
    for ( i = 0; i < N; i++ )
        fscanf(f, "%f %f\n", &points.x, &points.y);
    fclose(f);

    points[ N ] = points[ 0 ];

    double min = 100000;
    double tmp;
    for ( i = 0; i < N; ++i ) //цикл по граням
    {
        double max = 0;
        for (j = 0; j < N; j++) // цикл по точкам не принадлежищим грани
            if ( j != i && j != i+1 )
            {
                tmp = findDistance(points[j], points, points[i+1]);
                if (tmp > max)
                    max = tmp;
            }
            if (max < min)
                min = max;
    }

    f = fopen("output.txt", "wb");
    if (!f)
        return;

    fprintf(f, "%.3f\n", min);
    fclose(f);

    system("PAUSE");
    return;
}

И кстати говоря - пример, который ты привел, это не выпуклый многоугольник, так что считать проекцию будет не верно
19K
30 ноября 2007 года
Paradoxek
45 / / 24.10.2007
казалось что всё понял, а щас понял что ни чего не понял,
почему мне выдаёт что у квадрата с координатами
2 2
6 2
2 6
6 6
мин проекция 2.828
13K
30 ноября 2007 года
specter
113 / / 28.09.2007
Цитата: Paradoxek
казалось что всё понял, а щас понял что ни чего не понял,
почему мне выдаёт что у квадрата с координатами
2 2
6 2
2 6
6 6
мин проекция 2.828


А ты уверен, что это квадрат? Квадрат будет так:

 
Код:
2 2
6 2
6 6
2 6

Результат: 4.000
320
30 ноября 2007 года
m_Valery
1.0K / / 08.01.2007
Цитата: Paradoxek
:mad: упс, я понял одно, шо мозги мои спеклись



[COLOR="Red"]Я удалил одно сообщение,а ты следующее запостил.Ты собираешься на форуме описывать свое состояние здоровтья ? Зачем эти посты ? Такие посты согласно Правилам раздела удаляются,предупреждаю последний раз - получишь нарушение.[/COLOR]модератор.

19K
10 декабря 2007 года
Paradoxek
45 / / 24.10.2007
можно описать подробный алгоритм работы программы? порядок работы,описание функций, и какова структура программы?
19K
14 декабря 2007 года
Paradoxek
45 / / 24.10.2007
у меня есть некоторые вопросы, обьясните пожалуйсто
зачем нужен массив Point points[101];
и после этого не всё понятно с строками
fscanf(f, "%d\n", &N);
int i, j; //ну это понятно
for ( i = 0; i < N; i++ ) //для чего этот цикл?
fscanf(f, "%f %f\n", &points.x, &points.y); //тоже вроде понятно
points[ N ] = points[ 0 ]; //вот это зачем?
for ( i = 0; i < N; ++i ) //для чего этот цикл? что он делает?
double max = 0; //max = 0
for (j = 0; j < N; j++) // не понятно, для чего
if ( j != i && j != i+1 ) //так же
{
tmp = findDistance(points[j], points, points[i+1]); //вызов функции findDistance
if (tmp > max) //что тут делается
max = tmp; //--/--
}
if (max < min) //--/--
min = max; //--/--
19K
14 декабря 2007 года
Paradoxek
45 / / 24.10.2007
Цитата: specter
Попробую объяснить ;) Смотри сразу атач... рисовал в paint, так что не ругайте сильно :)

Теперь смотри - берез 2 точки - A и F... и считаем от прямой образованной этими точками расстояние до каждой вершины... получится 4 значения расстояний для точек B,C,D,E (см. рисунок)... в данном случае проекция будет равна расстоянию от прямой AF до точки C...



а почему ты взял именно эти 2 точки?

19K
15 декабря 2007 года
Paradoxek
45 / / 24.10.2007
по моему прога работает правильно только для 4-х уголника
19K
15 декабря 2007 года
Paradoxek
45 / / 24.10.2007
скажите пожалуйсто, как выбирать какие именно две точки брать, через которые проводится прямая.
19K
16 декабря 2007 года
Paradoxek
45 / / 24.10.2007
куда пропали добрые люди? сори за флуд( оч. надо
19K
18 декабря 2007 года
Paradoxek
45 / / 24.10.2007
а вы могли бы нарисовать блок схему к этой программе?
19K
20 января 2008 года
Paradoxek
45 / / 24.10.2007
короче, как объяснил препод это всё не правильно, тут всё намного проще,
например дан 3-угольник, abc. aс принадлежит у. bc-x
какая из сторон меньше, та и есть минимальная проекция.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог