(С++)Вычисление минимальной проекции выпуклого многоугольника
на плоскости х-у координатами вершин задан выпуклый многоугольник. Определить велечину его минимальной проекции на одну из осей.Программа должна читать данные из файла INPUT.TXT, содержащего: в первой строке-число вершин многоугольника N(2<N<100); в следующих N строках - по два вещественных числа - координаты х и у вершин (0<=x и у<=100). Программа должна вывести в фаил OUTPUT.TXT велечину минимальной проекции многоугольника на ось, вычесленную с точностью до 3-го знака после десятичной точки.
и плииз подскажите чё такое минимальная проекция, чем отличается от обычной проекции?
[COLOR="Red"]В названии темы надо указывать язык программирования.[/COLOR]модератор
Меня вот что интересует. Ты говорил, что мое утверждение полностью верное. Ты где-то нашел доказательство?
Нет, я доказательство не искал... просто на сколько я помню, то данная задача рассматривалась в курсе вышки ;)
И насчет того, что для невыпуклого можно взять разность между max-min
На счет минимума и максимума - это предположение. Если хочешь могу объяснить почему я считаю, что это будет работать :)
дайте ссылочку плиз где скачать?
А ты сможешь 2 гига вытянуть? ;) Лучше диск возьми у кого-нить или купи... проще будет. Называется Visual Studio 2005 (есть еще Visual Studio .net 2003).
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).
запускается и сразу вылетает
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 с параметрами? Если это файл не найдет программа завершает свою работу
если прога отработает нормально, то ты увидишь что-то типа "Нажмите любую клавишу для продолжения..."
a(4;6)
b(6;3.5)
c(6;2.5)
d(3;2)
e(2;1)
f(1.5;3)
разве его минимальная проекция будет равна 0???
У меня получилось 14.75 / sqrt(15.25) - примерно 3.78.
Если ты взял алгоритм для выпуклого многоугольника, естественно, он может дать неверный результат, поскольку твой шестиугольник - невыпуклый.
a(4;6)
b(6;3.5)
c(6;2.5)
d(3;2)
e(2;1)
f(1.5;3)
разве его минимальная проекция будет равна 0???
Не дочитал, что координаты вещественные ;) Вот тебе маленький фикс:
#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;
}
И кстати говоря - пример, который ты привел, это не выпуклый многоугольник, так что считать проекцию будет не верно
почему мне выдаёт что у квадрата с координатами
2 2
6 2
2 6
6 6
мин проекция 2.828
почему мне выдаёт что у квадрата с координатами
2 2
6 2
2 6
6 6
мин проекция 2.828
А ты уверен, что это квадрат? Квадрат будет так:
6 2
6 6
2 6
Результат: 4.000
[COLOR="Red"]Я удалил одно сообщение,а ты следующее запостил.Ты собираешься на форуме описывать свое состояние здоровтья ? Зачем эти посты ? Такие посты согласно Правилам раздела удаляются,предупреждаю последний раз - получишь нарушение.[/COLOR]модератор.
зачем нужен массив 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; //--/--
Теперь смотри - берез 2 точки - A и F... и считаем от прямой образованной этими точками расстояние до каждой вершины... получится 4 значения расстояний для точек B,C,D,E (см. рисунок)... в данном случае проекция будет равна расстоянию от прямой AF до точки C...
а почему ты взял именно эти 2 точки?
например дан 3-угольник, abc. aс принадлежит у. bc-x
какая из сторон меньше, та и есть минимальная проекция.