Результат работы программы

Условие

Выбрать три разные точки заданного на плоскости множества точек, составляющие треугольник наибольшего периметра.

Анализ задачи

Исходные данные и результат

Дано:

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 = Результат работы программы - student2.ru – длина отрезка (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)

Результат работы программы

• Было найдено одно из наиболее быстрых решений, которое нашло баланс между дополнительными проверками и простым перебором всех возможных комбинаций;

• Пройдя достаточное количество разнообразных тестов, программа ни разу не дала сбоя, всегда возвращая верные результаты;

• Программа без особых справляется с большим количеством входных данных за короткий срок.

Наши рекомендации