Условие
Выбрать три разные точки заданного на плоскости множества точек, составляющие треугольник наибольшего периметра.
Анализ задачи
• Исходные данные и результат
Дано:
nєN<=100
M={di|diєD,i=1,n}
D={(x,y) |x,yєR}
Результат: r1,r2,r3єD, fϵ{0,-1,-2}.
Решение:
LNG = 
– длина отрезка (x1,y1),(x2,y2)
PER = LNG(d1,d2)+LNG(d2,d3)+LNG(d3,d1) – периметр треугольника (d1,d2,d3)
CHK = a, если |(х2-x1)*(у3-y2)|=|(x3-x2)*(y2-y1)|, то a=0; иначе а=1 – проверка на треугольник (на то, что точки не лежат на одной прямой)
При e=3, max=-2
Повторять
Если n>=2, то
max=-1
|при i=1
|повторять
||при j=i+1
||повторять
per=PER(di,dj,de)
Если max<per, то если CHK (di,dj,de)=1, то max=per, p1=i,p2=j,p3=e; j=j+1 ||пока j<=e-1 ||i=i+1 |пока i<=e-2 |e=e+1 Пока e<=n 3.Структуры данных, используемые для представления исходных данных и результатов задачи Const int N=100- константа, определяющая максимальное количество вводимых точек. Внешнее представление исходных данных: натуральное число n и последовательность координат n точек, представленных в виде пар вещественных чисел, разделенных запятой. Внутреннее представление исходных данных: int n-количество введенных точек(n<=N) pnt A[N] –массив, являющегося программным представлением множества точек на плоскости - массив структур вида struct pnt{float x,y}, являющихся программным представлением точки в двухмерном пространстве, где и - соответствующие координаты точки. Внешнее представление результата: Последовательность координат точек, представленная в виде пар вещественных чисел или сообщение об ошибке. Внутреннее представление результата: struct max {float per, int p1,p2,p3} - структура, являющейся программным представлением треугольника c наибольшим периметром в двухмерном пространстве, где per – длина периметра и сигнал ошибки, p1,p2 и p3 – условные номера точек. pnt A[N] –массив, являющегося программным представлением множества точек на плоскости - массив структур вида struct pnt{float x,y}, являющихся программным представлением точки в двухмерном пространстве, где и - соответствующие координаты точки.
Укрупненный алгоритм решения задачи
Структура программы
• Составные части программы
Void IN(pnt A[N],int i) – считывает координаты точки. Вызывается как элемент основной.
A[N] – множество точек, i – номер считываемой.
Void OUT (pnt A[N],max n) – выводит координаты точек треугольника с наибольшим периметром. Вызывается как элемент основной.
A[N] – множество точек, n – треугольник с наибольшим периметром, содержащий координаты вершин.
Float LNG (pnt A[N],int a,int b) – высчитывает расстояние между двумя точками. Вызывается как элемент PER.
A[N] – множество точек, a,b – номера точек, расстояние между которыми вычисляются.
Float PER (pnt A[N],int a,int b,int c) – высчитывает периметр треугольника, заданного тремя вершинами. Вызывается как элемент основной, вызывает LNG.
A[N] – множество точек, a,b,c – номера вершин треугольника.
Int CHECK_LINE (pnt A[N], int a, int b, int c) – проверяет, принадлежат ли точки одной прямой. Вызывается какэлемент основной.
A[N] – множество точек, a,b,c – номера проверяемых точек.
Текст программы
#include <stdio.h>
#include <conio.h>
#include <math.h>
#define N 100
struct pnt
{
float x;
float y;
};
struct max
{
int p1,p2,p3;
float per;
};
void IN (pnt A[N],int i)
{
scanf ("%f",&A[i].x);
scanf ("%f",&A[i].y);
}
void OUT (pnt A[N],max n)
{
printf ("%f %f, ",A[n.p1].x,A[n.p1].y);
printf ("%f %f, ",A[n.p2].x,A[n.p2].y);
printf ("%f %f",A[n.p3].x,A[n.p3].y);
}
float LNG (pnt A[N],int a,int b)
{
float lng;
lng=sqrt((A[a].x-A[b].x)*(A[a].x-A[b].x)+(A[a].y-A[b].y)*(A[a].y-A[b].y));
return lng;
}
float PER (pnt A[N],int a,int b,int c)
{
float per;
per=LNG(A,a,b);
per+=LNG (A,b,c);
per+=LNG (A,c,a);
return per;
}
int CHECK_LINE (pnt A[N],int a,int b,int c)
{
float k1,k2;
k1=(A[a].x-A[b].x)*(A[b].y-A[c].y);
k2=(A[a].y-A[b].y)*(A[b].x-A[c].x);
if (fabs(k1)!=fabs(k2)) return 1;
else return 0;
}
void main ()
{
int n,i,j,e;
float per;
pnt A[N];
max permax;
permax.per=-2;
printf ("Input number:");
scanf ("%d",&n);
if (n>2)
{
permax.per=-1;
for (e=0;e<n;e++)
{
printf ("Input %d x,y:",e+1);
IN (A,e);
if (e>1)
for (i=0;i<=(e-2);i++)
for (j=i+1;j<=(e-1);j++)
{
per=PER (A,i,j,e);
if (permax.per<per)
if (CHECK_LINE (A,i,j,e)==1)
{
permax.per=per;
permax.p1=i;
permax.p2=j;
permax.p3=e;
}
}
}
if (permax.per!=-1) OUT (A,permax);
else printf ("Error: All points on one line");
}
else printf ("Error: Need more points");
getch();
}
Набор тестов
1) Тест на недостаточность точек
Входные данные: 2
Результат: “Error: Need more points"
2) Тест на отсутствие треугольника (точки повторяются)
Входные данные: 3, (2,2),(3,3),(2,2)
Результат: ”Error: All points on the one line ”
3) Тест на отсутствие треугольника (все точки лежат на одной прямой)
Входные данные: 4, (2,4),(3,5),(-4,-2),(-1,1)
Результат:”Error: All points on the one line ”
4)Тесты на принадлежность точек
Входные данные: 17, (2,0),(1;7),(-1.5,5.2),(6.1,-1.6),(0.2,-0.2),(2,0),(2,4),(3,5),(-4,-2),(-1,1),(3,3),(2,2),(4,5),(5,4),(6,5),(5,6),(0,0)
Результат: (1,7),(6.1,-1.6),(-4,-2)
Результат работы программы
• Было найдено одно из наиболее быстрых решений, которое нашло баланс между дополнительными проверками и простым перебором всех возможных комбинаций;
• Пройдя достаточное количество разнообразных тестов, программа ни разу не дала сбоя, всегда возвращая верные результаты;
• Программа без особых справляется с большим количеством входных данных за короткий срок.
