Задача:Точка на плоскости задаётся координатами Х и Y. Выбрать три
различных точки из заданного множества точек на плоскости так,
чтобы была минимальной разность между количествами точек,
лежащих внутри и вне треугольника с вершинами в выбранных
точках.
Все данные считываются из текстового файла. Формат:
1-я строка – количество точек n.
Следующие n строк – пары чисел (координаты точек из множества
точек).
Вот мой код:
различных точки из заданного множества точек на плоскости так,
чтобы была минимальной разность между количествами точек,
лежащих внутри и вне треугольника с вершинами в выбранных
точках.
Все данные считываются из текстового файла. Формат:
1-я строка – количество точек n.
Следующие n строк – пары чисел (координаты точек из множества
точек).
Вот мой код:
Код:
def Ind(A,n):
i=0
k=i
t=i
Min=1000
count=0
for i in range(0,n-1):
for k in range(i+1,n) :
for t in range(k+1,n+1):
if i!=0:
for Ck in range(0,i):
a=(A[i][0] - A[Ck][0]) * (A[k][1] - A[i][1]) - (A[k][0] - A[i][0]) * (A[i][1] - A[Ck][1])
b=(A[k][0] - A[Ck][0]) * (A[t][1] - A[k][1]) - (A[t][0] - A[k][0]) * (A[k][1] - A[Ck][1])
c=(A[t][0] - A[Ck][0]) * (A[i][1] - A[t][1]) - (A[i][0] - A[t][0]) * (A[t][1] - A[Ck][1])
if (a<0 and b<=0 and c<0) or (a>0 and b>=0 and c>0) or (a<=0 and b<0 and c<0) or (a>=0 and b>0 and c>0) or (a<0 and b<0 and c <=0) or (a>0 and b>0 and c>=0) :
count+=1
else:
for Cn in range(i+1,n+1):
a=(A[i][0] - A[Cn][0]) * (A[k][1] - A[i][1]) - (A[k][0] - A[i][0]) * (A[i][1] - A[Cn][1])
b=(A[k][0] - A[Cn][0]) * (A[t][1] - A[k][1]) - (A[t][0] - A[k][0]) * (A[k][1] - A[Cn][1])
c=(A[t][0] - A[Cn][0]) * (A[i][1] - A[t][1]) - (A[i][0] - A[t][0]) * (A[t][1] - A[Cn][1])
if (a<0 and b<=0 and c<0) or (a>0 and b>=0 and c>0) or (a<=0 and b<0 and c<0) or (a>=0 and b>0 and c>0) or (a<0 and b<0 and c <=0) or (a>0 and b>0 and c>=0) :
count+=1
if abs(count-(n-count))<Min:
Min=abs(count-(n-count))
return Min
n = int(input('Введите сколько всего строчек:'))
A = [[int(j) for j in input('Введите строчки\n').split()] for i in range(n)]
print(Ind(A,n))