#include <fstream.h>
#include <iomanip.h>
voud main()
{
double minx,miny,maxx,maxy;
ifstream inf("input.txt");
int n;
inf>>n;
double x,y;
for (i=0;i<n;i++)
{
inf>>x>>y;
if (i==0||x<minx)
minx=x;
if (i==0||y<miny)
minx=y;
if (i==0||x>maxx)
maxx=x;
if (i==0||y>maxy)
maxx=y;
}
inf.close();
ofstream outf("OUTFILE.TXT");
outf.precision(3);
if (maxx-minx<maxy-maxy)
outf<<maxx-minx;
else
outf<<maxy-miny;
outf.close();
}
(С++)Вычисление минимальной проекции выпуклого многоугольника
С++
на плоскости х-у координатами вершин задан выпуклый многоугольник. Определить велечину его минимальной проекции на одну из осей.Программа должна читать данные из файла INPUT.TXT, содержащего: в первой строке-число вершин многоугольника N(2<N<100); в следующих N строках - по два вещественных числа - координаты х и у вершин (0<=x и у<=100). Программа должна вывести в фаил OUTPUT.TXT велечину минимальной проекции многоугольника на ось, вычесленную с точностью до 3-го знака после десятичной точки.
и плииз подскажите чё такое минимальная проекция, чем отличается от обычной проекции?
[COLOR="Red"]В названии темы надо указывать язык программирования.[/COLOR]модератор
на плоскости х-у координатами вершин задан выпуклый многоугольник. Определить велечину его минимальной проекции на одну из осей.Программа должна читать данные из файла INPUT.TXT, содержащего: в первой строке-число вершин многоугольника N(2<N<100); в следующих N строках - по два вещественных числа - координаты х и у вершин (0<=x и у<=100). Программа должна вывести в фаил OUTPUT.TXT велечину минимальной проекции многоугольника на ось, вычесленную с точностью до 3-го знака после десятичной точки.
и плииз подскажите чё такое минимальная проекция, чем отличается от обычной проекции?
[COLOR="Red"]В названии темы надо указывать язык программирования.[/COLOR]модератор
:confused: простите не знал) С++
Если не поворачивать, тогда просто:
Код:
спасибо большое) только она не работает, чё то траблы с библиотеками какието) ну не важно, мне главное сам алгоритм)) пасиб)
Цитата: wanja
Если не поворачивать, тогда просто:
Код:
#include <fstream.h>
#include <iomanip.h>
voud main()
{
double minx,miny,maxx,maxy;
ifstream inf("input.txt");
int n;
inf>>n;
double x,y;
for (i=0;i<n;i++)
{
inf>>x>>y;
if (i==0||x<minx)
minx=x;
if (i==0||y<miny)
minx=y;
if (i==0||x>maxx)
maxx=x;
if (i==0||y>maxy)
maxx=y;
}
inf.close();
ofstream outf("OUTFILE.TXT");
outf.precision(3);
if (maxx-minx<maxy-maxy)
outf<<maxx-minx;
else
outf<<maxy-miny;
outf.close();
}
#include <iomanip.h>
voud main()
{
double minx,miny,maxx,maxy;
ifstream inf("input.txt");
int n;
inf>>n;
double x,y;
for (i=0;i<n;i++)
{
inf>>x>>y;
if (i==0||x<minx)
minx=x;
if (i==0||y<miny)
minx=y;
if (i==0||x>maxx)
maxx=x;
if (i==0||y>maxy)
maxx=y;
}
inf.close();
ofstream outf("OUTFILE.TXT");
outf.precision(3);
if (maxx-minx<maxy-maxy)
outf<<maxx-minx;
else
outf<<maxy-miny;
outf.close();
}
а если поворачивать?
Тогда думать надо. :)
подумайте пожааалуйсто))) очень надо, курсовая горит, а я чё то ваще не могу вникнуть в эту прогу((
и что за inf>>n;
не могу понять что это,
ну и соответственно inf>>x>>y
короче что делат inf и зачем он) воть)
и что за inf>>n;
не могу понять что это,
ну и соответственно inf>>x>>y
короче что делат inf и зачем он) воть)
Минимальная проекция = грубо говоря, наименьшая длина "тени", которую фигура отбросит на ось.
Без вращения тут никак не обойтись, но вся прелесть в том, что вращать можно вокруг любой (!) точки. Задача сводится к поиску такого угла поворота, при котором "тень" на ось минимальна.
Насколько помню, преобразование координат точки при повороте относительно начала координат на угол B по часовой стрелке:
R = sqrt(x*x + y*y),
A = arc tan(x/y)
Xnew = R * cos(A + B)
Ynew = R * sin(A + B)
Значит, для каждого нового угла нужно пересчитать координаты всех вершин, определить размер "тени", ну и вращать до победного!
В конце можно уменьшать шаг изменения угла B, чтобы найти его с нужной точностью.
Без вращения тут никак не обойтись, но вся прелесть в том, что вращать можно вокруг любой (!) точки. Задача сводится к поиску такого угла поворота, при котором "тень" на ось минимальна.
Насколько помню, преобразование координат точки при повороте относительно начала координат на угол B по часовой стрелке:
R = sqrt(x*x + y*y),
A = arc tan(x/y)
Xnew = R * cos(A + B)
Ynew = R * sin(A + B)
Значит, для каждого нового угла нужно пересчитать координаты всех вершин, определить размер "тени", ну и вращать до победного!
В конце можно уменьшать шаг изменения угла B, чтобы найти его с нужной точностью.
спасибо большое) ппц мне помучиться придётся)):(
а кто может написать полностью рабочую программу?)):D
а кто может написать полностью рабочую программу?)):D
Так ведь угол поворота - величина непрерывная :) с каким шагом поворачивать-то?
Математическая интуиция мне подсказывает, что при минимальной проекции выпуклого многоугольника по-любому левый или правый (а может, и оба) "края" тени будут отбрасываться какой-то стороной, т. е. одна из сторон (самая "левая" или самая "правая") будут перпендикулярны к оси, на которую проецируем. Хотя такое утверждение чисто интуитивно и его еще надо доказать :)
Если интуиция не подводит, для N-угольника достаточно рассмотреть N вариантов угла поворота. В каждом i-м варианте i-я грань располагается вертикально (если проецируем на ось Ox).
Математическая интуиция мне подсказывает, что при минимальной проекции выпуклого многоугольника по-любому левый или правый (а может, и оба) "края" тени будут отбрасываться какой-то стороной, т. е. одна из сторон (самая "левая" или самая "правая") будут перпендикулярны к оси, на которую проецируем. Хотя такое утверждение чисто интуитивно и его еще надо доказать :)
Если интуиция не подводит, для N-угольника достаточно рассмотреть N вариантов угла поворота. В каждом i-м варианте i-я грань располагается вертикально (если проецируем на ось Ox).
Стоп. Дошло. Действительно, рассматриваем N вариантов. Но зачем выполнять проекцию? Длина проекции будет совпадать (раз уж многоугольник выпуклый) с максимальным расстоянием от той самой "вертикальной" грани до какой-либо из вершин.
Итак, алгоритм.
МинПроекция = 100000000 // Какое-то заведомо большое число
В цикле для каждой грани (G):
МаксРасстояниеДаннойГрани = 0;
Подцикл для каждой вершины, не принадлежащей этой грани (V[j])
Если расстояние от G до V[j] > МаксРасстояниеДаннойГрани тогда
МаксРасстояниеДаннойГрани = расстояние от G до V[j]
Конец подцикла
Если МаксРасстояниеДаннойГрани < МинПроекция тогда
МинПроекция = МаксРасстояниеДаннойГрани
Конец цикла
Думаю, всяко быстрее, чем строить реальную проекцию.
Итак, алгоритм.
МинПроекция = 100000000 // Какое-то заведомо большое число
В цикле для каждой грани (G):
МаксРасстояниеДаннойГрани = 0;
Подцикл для каждой вершины, не принадлежащей этой грани (V[j])
Если расстояние от G до V[j] > МаксРасстояниеДаннойГрани тогда
МаксРасстояниеДаннойГрани = расстояние от G до V[j]
Конец подцикла
Если МаксРасстояниеДаннойГрани < МинПроекция тогда
МинПроекция = МаксРасстояниеДаннойГрани
Конец цикла
Думаю, всяко быстрее, чем строить реальную проекцию.
спасибо большое))
я как понимаю вы все опытные программеры))
вот такие вот задачки задают студенду 2-го курса, не решу выкинут из универа:(
спасибо что помогаете)
я как понимаю вы все опытные программеры))
вот такие вот задачки задают студенду 2-го курса, не решу выкинут из универа:(
спасибо что помогаете)
может кто ни будь ещё подумает над этой задачкой?:)
Цитата: Paradoxek
может кто ни будь ещё подумает над этой задачкой?:)
Могу написать решение, мне не тяжело ;) только дай ссылку на формулу нахождения расстояния от точки до прямой на плоскости
Цитата: specter
Могу написать решение, мне не тяжело ;) только дай ссылку на формулу нахождения расстояния от точки до прямой на плоскости
Потел вчера и сегодня над этой задачей (расстояние от точки (x1, y1) до прямой (ax+by+c = 0)). Вот, кажется, такая формула.
L = abs (x1*a + y1*b + c) / sqrt (a^2 + b^2)
Проверил на двух примерах, работает.
Если вместо коэффициентов (a, b, c) известны две точки, через которые проходит прямая, формулы завтра вычислю и выложу.
Цитата: cheburator
Если вместо коэффициентов (a, b, c) известны две точки, через которые проходит прямая, формулы завтра вычислю и выложу.
Естественно известны только 2 точки ;)
Если прямая проходит через точки (x2, y2) и (x3, y3), уравнение прямой такое:
(y2-y3)*x + (x3-x2)*y + x2*y3 - x3*y2 = 0,
т. е. коэффициенты:
a = y2-y3
b = x3-x2
c = x2*y3 - x3*y2
Еще вся прелесть в том, что если координаты вершин многоугольника - целые (т. е. имеем дело с пикселями на экране), многие числа из всех формул получаются целыми.
Вот что примерно получается.
P. S. Код не тестировал
(y2-y3)*x + (x3-x2)*y + x2*y3 - x3*y2 = 0,
т. е. коэффициенты:
a = y2-y3
b = x3-x2
c = x2*y3 - x3*y2
Еще вся прелесть в том, что если координаты вершин многоугольника - целые (т. е. имеем дело с пикселями на экране), многие числа из всех формул получаются целыми.
Вот что примерно получается.
Код:
int vcount; // Число вершин
int x[], y[]; // Массив координат вершин (естественно, надо объявить нормально, или заменить std::vector-ами)
double minproj = 1000000.0;
double L, a2b2;
int idx2, a, b, c;
for (int i = 0; i<vcount; ++i) // Цикл по сторонам многоугольника
{
// Сторона образована вершинами <i, i+1> или <i, 0> - если i - последняя вершина
idx2 = (i == vcount-1) ? 0 : i+1;
a = y-y[idx2];
b = x[idx2]-x;
c = x*y[idx2] - x[idx2]*y;
a2b2 = sqrt (a*a + b*b);
double maxlen = 0.0;
for (int v = i+2; v < vcount; ++v) // Цикл по вершинам, не лежащим на этой стороне (первая часть)
{
L = abs (a*x[v] + b*y[v] + c) / a2b2;
if (L > maxlen)
maxlen = L;
}
for (int v = 0; v < i; ++v) // вторая часть
{
L = abs (a*x[v] + b*y[v] + c) / a2b2;
if (L > maxlen)
maxlen = L;
}
if (maxlen < minproj)
minproj = maxlen;
}
int x[], y[]; // Массив координат вершин (естественно, надо объявить нормально, или заменить std::vector-ами)
double minproj = 1000000.0;
double L, a2b2;
int idx2, a, b, c;
for (int i = 0; i<vcount; ++i) // Цикл по сторонам многоугольника
{
// Сторона образована вершинами <i, i+1> или <i, 0> - если i - последняя вершина
idx2 = (i == vcount-1) ? 0 : i+1;
a = y-y[idx2];
b = x[idx2]-x;
c = x*y[idx2] - x[idx2]*y;
a2b2 = sqrt (a*a + b*b);
double maxlen = 0.0;
for (int v = i+2; v < vcount; ++v) // Цикл по вершинам, не лежащим на этой стороне (первая часть)
{
L = abs (a*x[v] + b*y[v] + c) / a2b2;
if (L > maxlen)
maxlen = L;
}
for (int v = 0; v < i; ++v) // вторая часть
{
L = abs (a*x[v] + b*y[v] + c) / a2b2;
if (L > maxlen)
maxlen = L;
}
if (maxlen < minproj)
minproj = maxlen;
}
P. S. Код не тестировал
Цитата: cheburator
Вот что примерно получается.
...
О боже :eek: Лично я ничего почти ничего не понял из этого кода... Надеюсь ты не обидишся, если я предложу свой вариант ;)
Код:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct Point
{
int x;
int 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, "%d %d\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;
}
#include <stdlib.h>
#include <math.h>
struct Point
{
int x;
int 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, "%d %d\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;
}
Цитата: specter
Код:
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;
}
{
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;
}
При i == N-1 (последняя итерация) на что будет ссылаться points[i+1] ?
Цитата: specter
Код:
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);
}
...
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;
}
{
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);
}
...
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;
}
Тебе не кажется, что коэффициенты a, b, c, а также sqrt(a*a + b*b) вычисляются избыточно, в цикле, ведь points, points[i+1] не меняются?
А также a, b, c - целочисленные, раз уж за основу взят тип Point.
Цитата: cheburator
При i == N-1 (последняя итерация) на что будет ссылаться points[i+1] ?
>> points[ N ] = points[ 0 ];
Цитата: cheburator
Тебе не кажется, что коэффициенты a, b, c, а также sqrt(a*a + b*b) вычисляются избыточно, в цикле, ведь points, points[i+1] не меняются?
А также a, b, c - целочисленные, раз уж за основу взят тип Point.
А также a, b, c - целочисленные, раз уж за основу взят тип Point.
Ты прав, писалось это на скорую руку, но данный вариант более доступен для понимания, тем более что автор явно не искушен в программировании ;) вообще-то можно весь цикл нахождения проекции для одной грани вынести в функцию и оптимизировать вычисления, было бы красивее, но мне лень :D
а что за прямую вы находите?
и что такое a.b.c.?
и что такое a.b.c.?
и что значит ВЕЛЕЧИНА минимальной проекции? расстояние от данного многоугольника до оси?
Цитата: Paradoxek
и что значит ВЕЛЕЧИНА минимальной проекции? расстояние от данного многоугольника до оси?
От многоугольника падает тень (солнце в зените; рассматривается плоский случай - мир двумерный). Многоугольник может быть повернут как угодно. Найти минимальную длину тени.
Цитата: Paradoxek
а что за прямую вы находите?
и что такое a.b.c.?
и что такое a.b.c.?
Читаем предыдущие сообщения в теме.
честно говоря я мало что понял, с кодом конечно разберусь, мне сам смысл задачи не понятен, можно его обьяснить,
окуда ваще эту тень взять,
с геометрией проблемы у меня(((
окуда ваще эту тень взять,
с геометрией проблемы у меня(((
Я тут подумал, и придумал алгоритм: Перебираем все пары точек, и проверяем, попадают ли перпендикуляры к отрезку междк ними из этих точек вутрь многоугольника(острый ли угол между этим отрезком и отрезком от его конца до соседних точек), и считаем между подходящими минимальный.
Цитата: wanja
Я тут подумал, и придумал алгоритм: Перебираем все пары точек, и проверяем, попадают ли перпендикуляры к отрезку междк ними из этих точек вутрь многоугольника(острый ли угол между этим отрезком и отрезком от его конца до соседних точек), и считаем между подходящими минимальный.
а можешь написать?
Цитата: Paradoxek
честно говоря я мало что понял, с кодом конечно разберусь, мне сам смысл задачи не понятен, можно его обьяснить,
окуда ваще эту тень взять,
с геометрией проблемы у меня(((
окуда ваще эту тень взять,
с геометрией проблемы у меня(((
Попробую объяснить ;) Смотри сразу атач... рисовал в paint, так что не ругайте сильно :)
Пусть есть многоугольник ABCDEF, как найти его минимальную проекцию (допустим на ось X)? Было высказано предположение (кстати полностью верное), что при при минимальной проекции одна сторона будет перпендикулярна оси X (ее проекция будет равна 0)... таким образом чтобы найти проекцию на ось нужно повернуть фигуру на определенный угол, чтобы одна из граней была перпендикулярна оси Х... но это сложно... намного проще не поворачивать всю фигуру, а посчитать расстояние от этой грани (точнее от прямой образованой этой гранью) до других точек.
Теперь смотри - берез 2 точки - A и F... и считаем от прямой образованной этими точками расстояние до каждой вершины... получится 4 значения расстояний для точек B,C,D,E (см. рисунок)... в данном случае проекция будет равна расстоянию от прямой AF до точки C...
Теперь по поводу коэффициентов abc - они нужны для расчета формулы прямой (так как в общем виде прямая задается формулой a*x+b*y+c=0). Зная коэффициенты a,b,c мы можем по формуле найти кратчайшее расстояние от этой прямой до любой точки (что мы и делаем в проге)
Цитата: wanja
Я тут подумал, и придумал алгоритм: Перебираем все пары точек, и проверяем, попадают ли перпендикуляры к отрезку междк ними из этих точек вутрь многоугольника(острый ли угол между этим отрезком и отрезком от его конца до соседних точек), и считаем между подходящими минимальный.
Нихрена себе завернул :D
Ты перефразировал в извращенной и усложненной форме то, что уже обсуждалось выше и уже реализовано... и, кстати, твой алгоритм будет работать только на выпуклых многоугольниках
Цитата: Paradoxek
честно говоря я мало что понял, с кодом конечно разберусь, мне сам смысл задачи не понятен, можно его обьяснить,
окуда ваще эту тень взять,
с геометрией проблемы у меня(((
окуда ваще эту тень взять,
с геометрией проблемы у меня(((
На следующем рисунке можешь посмотреть что такое проекция (на ось X и на ось Y):
блин!!!! у меня нет слов))) вот чего мне не хватало, конкретных обьяснений с рисунками) спасибо огромное))):D
Цитата: Paradoxek
блин!!!! у меня нет слов))) вот чего мне не хватало, конкретных обьяснений с рисунками) спасибо огромное))):D
Пжалста, обращайся ;)
Уточнение.
Тема касается только выпуклых многоугольников.
Для невыпуклых многоугольников основа алгоритма - фраза
"Было высказано предположение (кстати полностью верное), что при при минимальной проекции одна сторона будет перпендикулярна оси X (ее проекция будет равна 0)..."
остается верной, но некоторые стороны надо в нашем алгоритме исключать из рассмотрения - а именно, те стороны, для которых существуют вершины, расположенные как в одной полуплоскости от нее, так и в другой (проще говоря, стороны, из-за которых многоугольник невыпуклый). Поскольку такая сторона как-раз таки не может быть "краем" тени. Для приведенных тут рисунков - это стороны CD и DE.
Тема касается только выпуклых многоугольников.
Для невыпуклых многоугольников основа алгоритма - фраза
"Было высказано предположение (кстати полностью верное), что при при минимальной проекции одна сторона будет перпендикулярна оси X (ее проекция будет равна 0)..."
остается верной, но некоторые стороны надо в нашем алгоритме исключать из рассмотрения - а именно, те стороны, для которых существуют вершины, расположенные как в одной полуплоскости от нее, так и в другой (проще говоря, стороны, из-за которых многоугольник невыпуклый). Поскольку такая сторона как-раз таки не может быть "краем" тени. Для приведенных тут рисунков - это стороны CD и DE.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct Point
{
int x;
int 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, "%d %d\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;
кто ни будь проверял этот код? не хочет работать(( не пойму почему
#include <stdlib.h>
#include <math.h>
struct Point
{
int x;
int 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, "%d %d\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;
кто ни будь проверял этот код? не хочет работать(( не пойму почему
C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
[Warning] In function `double:
17 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
[Warning] passing
17 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
[Warning] argument
/Documents and Settings/Âàäè/Ìîè äîêóìåíòû/Untitled1.cpp C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\C
At global scope:
21 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
`main' must
C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
[Warning] In function `int:
25 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
return-statement
57 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
return-statement
63 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
return-statement
64 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
parse error at
вот такие вот ошибки выдаёт
[Warning] In function `double:
17 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
[Warning] passing
17 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
[Warning] argument
/Documents and Settings/Âàäè/Ìîè äîêóìåíòû/Untitled1.cpp C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\C
At global scope:
21 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
`main' must
C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
[Warning] In function `int:
25 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
return-statement
57 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
return-statement
63 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
return-statement
64 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
parse error at
вот такие вот ошибки выдаёт
Цитата: Paradoxek
C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
[Warning] In function `double:
17 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
[Warning] passing
17 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
[Warning] argument
/Documents and Settings/Âàäè/Ìîè äîêóìåíòû/Untitled1.cpp C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\C
At global scope:
21 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
`main' must
C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
[Warning] In function `int:
25 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
return-statement
57 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
return-statement
63 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
return-statement
64 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
parse error at
вот такие вот ошибки выдаёт
[Warning] In function `double:
17 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
[Warning] passing
17 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
[Warning] argument
/Documents and Settings/Âàäè/Ìîè äîêóìåíòû/Untitled1.cpp C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\C
At global scope:
21 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
`main' must
C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
[Warning] In function `int:
25 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
return-statement
57 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
return-statement
63 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
return-statement
64 C:\Documents and Settings\Âàäè\Ìîè äîêóìåíòû\Untitled1.cpp
parse error at
вот такие вот ошибки выдаёт
Чем компилишь?
Цитата: cheburator
Уточнение.
Тема касается только выпуклых многоугольников.
Для невыпуклых многоугольников основа алгоритма - фраза
"Было высказано предположение (кстати полностью верное), что при при минимальной проекции одна сторона будет перпендикулярна оси X (ее проекция будет равна 0)..."
остается верной, но некоторые стороны надо в нашем алгоритме исключать из рассмотрения - а именно, те стороны, для которых существуют вершины, расположенные как в одной полуплоскости от нее, так и в другой (проще говоря, стороны, из-за которых многоугольник невыпуклый). Поскольку такая сторона как-раз таки не может быть "краем" тени. Для приведенных тут рисунков - это стороны CD и DE.
Тема касается только выпуклых многоугольников.
Для невыпуклых многоугольников основа алгоритма - фраза
"Было высказано предположение (кстати полностью верное), что при при минимальной проекции одна сторона будет перпендикулярна оси X (ее проекция будет равна 0)..."
остается верной, но некоторые стороны надо в нашем алгоритме исключать из рассмотрения - а именно, те стороны, для которых существуют вершины, расположенные как в одной полуплоскости от нее, так и в другой (проще говоря, стороны, из-за которых многоугольник невыпуклый). Поскольку такая сторона как-раз таки не может быть "краем" тени. Для приведенных тут рисунков - это стороны CD и DE.
Для невыпуклого многоугольника можно просто найти минимум и максисум... если они будут разного знака, то значение проекции для данной ситуации будет равно max-min
Цитата: specter
Для невыпуклого многоугольника можно просто найти минимум и максисум... если они будут разного знака, то значение проекции для данной ситуации будет равно max-min
Вполне возможно.
Меня вот что интересует. Ты говорил, что мое утверждение полностью верное. Ты где-то нашел доказательство?
И насчет того, что для невыпуклого можно взять разность между max-min