Определить номера точек, которые могут являться вершинами квадрата

@Maloy1337 · Регистрация: 28.09.2020

Студворк — интернет-сервис помощи студентам

В одномерном массиве с четным количеством элементов (2N) находятся координаты N точек плоскости. Они располагаются в следующем порядке: х1 y1 x2, y2, х3, уЗ и тд. (xi ,yi — целые). Определить номера точек, которые могут являться вершинами квадрата. Вот пример только с радиусом

Python
1
2
3
4
5
6
7
8
9
10
import random
n = int(input("Введите количество точек: "))
a = []
radius = 0
for i in range(2*n):
    r = random.randint(0,50) if random.randint(1,11) % 2 == 0 else random.randint(-20,0)
    a.append(r)
    if radius < abs(r): radius = abs(r)
    print("x",i//2+1,": ",r,sep="",end="\t") if i%2==0 else print("y",i//2+1,": ",r,sep="")
print("\nОкружность с центром в начале координат и радиусом", radius)

Добавлено через 5 минут
И если можно скрин с результатами вывода

@КулХацкеръ · 06.12.2020, 22:35

Реализовывал алгоритм от Gdez около двух часов, получилось следующее:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
from itertools import permutations
 
class Point:
    def __init__(self, x, y, index):
        self.x = x
        self.y = y
        self.index = index
 
class Vector:
    #Вектор = (xa - xb, ya - yb)
    #для отрезка "ab".
    def __init__(self, a, b):
        self.a = a
        self.b = b
        self.dx = a.x - b.x
        self.dy = a.y - b.y
 
N = 0
points = []
 
def read():
    global N, points
    with open('input.txt') as f:
        arr = [int(t) for t in f.readline().split()]
    N = len(arr) // 2
    points = []
    for i in range(N):
        points.append(Point(arr[i * 2], arr[i * 2 + 1], i + 1))
 
def check_vectors(vec1, vec2, vec3, vec4):
    #Для существования квадрата
    #достаточно и необходимо 4
    #различных (координатно) по
    #знакам, но одинаковых по
    #модулю ((-1,-3)==(1,3)==
    #==(3,-1)==(-3,1)) вектора.
    return (vec1.dx == vec2.dy and \
    vec1.dy == -vec2.dx or \
    vec1.dx == -vec2.dy and \
    vec1.dy == vec2.dx) and \
    (vec2.dx == vec3.dy and \
    vec2.dy == -vec3.dx or \
    vec2.dx == -vec3.dy and \
    vec2.dy == vec3.dx) and \
    (vec3.dx == vec4.dy and \
    vec3.dy == -vec4.dx or \
    vec3.dx == -vec4.dy and \
    vec3.dy == vec4.dx)
 
def square_exists(vec1, vec2, vec3, vec4):
    #Перебор всех перестановок
    #векторов и вызов check_vectors
    #для каждой перестановки,
    #пока не доказано существование
    #квадрата или не перебраны
    #все перестановки.
    perms = permutations([vec1, vec2, vec3, vec4])
    for vecs in perms:
        if check_vectors(vecs[0], vecs[1], vecs[2], vecs[3]):
            return True
    return False 
    
def solve():
    #...проход по массиву точек
    #для каждой по возрастанию
    #индексов ищуться векторы
    #направления отрезков с
    #другими оставшимися точками...
    vectors = []
    for i in range(N - 1):
        a = points[i]
        for j in range(i + 1, N):
            b = points[j]
            vectors.append(Vector(a, b))
    
    f = open('output.txt', 'w')
    
    #Перебор всех четверок векторов.
    M = len(vectors)
    indices = set()
    for i1 in range(M - 3):
        vec1 = vectors[i1]
        for i2 in range(i1 + 1, M - 2):
            vec2 = vectors[i2]
            for i3 in range(i2 + 1, M - 1):
                vec3 = vectors[i3]
                for i4 in range(i3 + 1, M):
                    vec4 = vectors[i4]
                    #print(vec1.dx, vec2.dx, vec3.dx, vec4.dx)
                    #print(vec1.dy, vec2.dy, vec3.dy, vec4.dy)
                    #print()
                    if square_exists(vec1, vec2, vec3, vec4):
                        
                        indices.clear()
                        indices.add(vec1.a.index)
                        indices.add(vec1.b.index)
                        indices.add(vec2.a.index)
                        indices.add(vec2.b.index)
                        indices.add(vec3.a.index)
                        indices.add(vec3.b.index)
                        indices.add(vec4.a.index)
                        indices.add(vec4.b.index)
                        s = ('Точки с номерами ' +
                        ', '.join(map(str, sorted(indices))) +
                        ' образуют квадрат.')
                        f.write(s[::-1].replace(' ,', ' и ', 1)[::-1])
                        f.write('\n')
    f.close()
                        
 
read()
solve()

Что думаете?

@Gdez · 06.12.2020, 22:37

Catstail, понятно

- чужой "синтаксис" поправил...

isaak, там четыре точки...
Ну и код не мой - проверка в нем при определенных значениях "вылетает"

@Catstail · 06.12.2020, 22:39

Сообщение от КулХацкеръ

Что думаете?

- громоздко

@Gdez · 06.12.2020, 22:41

КулХацкеръ,

но ппц

и не лень же... Завидую терпению.

Добавлено через 2 минуты
КулХацкеръ, Можно combinations перебрать все "четверки" из N. И на проверку "отправлять"

@КулХацкеръ · 06.12.2020, 22:55

Сообщение от Catstail

- громоздко

Наверное. Это можно как-то улучшить?

Добавлено через 3 минуты

Сообщение от Gdez

Можно combinations перебрать все "четверки" из N. И на проверку "отправлять"

Ага, понял. Попробую переделать.

Добавлено через 9 минут

Python
1
from itertools import combinations, permutations

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
    #Перебор всех четверок векторов.
    M = len(vectors)
    indices = set()
    combs = combinations(vectors, 4)
    for vecs in combs:
        vec1 = vecs[0]
        vec2 = vecs[1]
        vec3 = vecs[2]
        vec4 = vecs[3]
        if square_exists(vec1, vec2, vec3, vec4):
            indices.clear()
            indices.add(vec1.a.index)
            indices.add(vec1.b.index)
            indices.add(vec2.a.index)
            indices.add(vec2.b.index)
            indices.add(vec3.a.index)
            indices.add(vec3.b.index)
            indices.add(vec4.a.index)
            indices.add(vec4.b.index)
            s = ('Точки с номерами ' +
            ', '.join(map(str, sorted(indices))) +
            ' образуют квадрат.')
            f.write(s[::-1].replace(' ,', ' и ', 1)[::-1])
            f.write('\n')
    f.close()

Так?

@isaak · 06.12.2020, 22:57

КулХацкеръ, круто спасибо за терпение и упорство.

@КулХацкеръ · 06.12.2020, 23:00

Или даже так:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    #Перебор всех четверок векторов.
    M = len(vectors)
    indices = set()
    combs = combinations(vectors, 4)
    for vecs in combs:
        if square_exists(vecs[0], vecs[1], vecs[2], vecs[3]):
            indices.clear()
            for i in range(4):
                indices.add(vecs[i].a.index)
                indices.add(vecs[i].b.index)
            s = ('Точки с номерами ' +
            ', '.join(map(str, sorted(indices))) +
            ' образуют квадрат.')
            f.write(s[::-1].replace(' ,', ' и ', 1)[::-1])
            f.write('\n')
    f.close()

Добавлено через 1 минуту
isaak, спасибо, я старался

.

@Catstail · 06.12.2020, 23:03

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from random import randint
 
def task(arr):
    x=arr[0::2]
    y=arr[1::2]
    n=len(x)
    for i in range(n-3):
        for j in range(i+1,n-2):
            for k in range(j+1,n-1):
                for p in range(k+1,n):
                    xx=[x[i],x[j],x[k],x[p]]
                    yy=[y[i],y[j],y[k],y[p]]
                    if isSquare(xx,yy):
                        print(i,j,k,p)
                        
def isSquare(x,y):
    d=[0,0,0,0,0,0]
    k=0
    for i in range(3):
        for j in range(i+1,4):
            p=x[i]-x[j]
            q=y[i]-y[j]
            d[k]=p*p+q*q
            k+=1
    for a in d:
        if not d.count(a) in [2,4]:
            return False
    return True        
 
coords=[randint(-10,10) for i in range(100)]
task(coords)

@Gdez · 06.12.2020, 23:18

Catstail, такие решения (циклами) видел. Просто интересно, что быстрее: комбинации модулем или просто перебором в цикле?

Добавлено через 1 минуту
А так весь цимес этой задачи , по-моему, в функции определения квадрата

@Catstail · 06.12.2020, 23:22

Сообщение от Gdez

А так весь цимес этой задачи , по-моему, в функции определения квадрата

- именно!

@isaak · 06.12.2020, 23:24

КулХацкеръ,
Что у меня в последнем коде файл output.txt пустой выходит. В чем может быть проблема????

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
from itertools import combinations, permutations
 
 
class Point:
    def __init__(self, x, y, index):
        self.x = x
        self.y = y
        self.index = index
 
class Vector:
    #Вектор = (xa - xb, ya - yb)
    #для отрезка "ab".
    def __init__(self, a, b):
        self.a = a
        self.b = b
        self.dx = a.x - b.x
        self.dy = a.y - b.y
 
N = 0
points = []
 
def read():
    global N, points
    with open('input.txt') as f:
        arr = [int(t) for t in f.readline().split()]
    N = len(arr) // 2
    points = []
    for i in range(N):
        points.append(Point(arr[i * 2], arr[i * 2 + 1], i + 1))
 
def check_vectors(vec1, vec2, vec3, vec4):
    #Для существования квадрата
    #достаточно и необходимо 4
    #различных (координатно) по
    #знакам, но одинаковых по
    #модулю ((-1,-3)==(1,3)==
    #==(3,-1)==(-3,1)) вектора.
    return (vec1.dx == vec2.dy and \
    vec1.dy == -vec2.dx or \
    vec1.dx == -vec2.dy and \
    vec1.dy == vec2.dx) and \
    (vec2.dx == vec3.dy and \
    vec2.dy == -vec3.dx or \
    vec2.dx == -vec3.dy and \
    vec2.dy == vec3.dx) and \
    (vec3.dx == vec4.dy and \
    vec3.dy == -vec4.dx or \
    vec3.dx == -vec4.dy and \
    vec3.dy == vec4.dx)
 
def square_exists(vec1, vec2, vec3, vec4):
    #Перебор всех перестановок
    #векторов и вызов check_vectors
    #для каждой перестановки,
    #пока не доказано существование
    #квадрата или не перебраны
    #все перестановки.
    perms = permutations([vec1, vec2, vec3, vec4])
    for vecs in perms:
        if check_vectors(vecs[0], vecs[1], vecs[2], vecs[3]):
            return True
    return False 
    
def solve():
    #...проход по массиву точек
    #для каждой по возрастанию
    #индексов ищуться векторы
    #направления отрезков с
    #другими оставшимися точками...
    vectors = []
    for i in range(N - 1):
        a = points[i]
        for j in range(i + 1, N):
            b = points[j]
            vectors.append(Vector(a, b))
    
    f = open('output.txt', 'w')
    M = len(vectors)
    indices = set()
    combs = combinations(vectors, 4)
    for vecs in combs:
        if square_exists(vecs[0], vecs[1], vecs[2], vecs[3]):
            indices.clear()
            for i in range(4):
                indices.add(vecs[i].a.index)
                indices.add(vecs[i].b.index)
            s = ('Точки с номерами ' +
            ', '.join(map(str, sorted(indices))) +
            ' образуют квадрат.')
            f.write(s[::-1].replace(' ,', ' и ', 1)[::-1])
            f.write('\n')
    f.close()
    read()
solve()

@КулХацкеръ · 06.12.2020, 23:28

У, Catstail, это интересно!

В следующий вечер будет что поизучать.
А сейчас уже спа-а-ать охота

.

Добавлено через 1 минуту
isaak, read() поставь на 4 пробела ближе к левому краю (убери отступ).

@eaa · 06.12.2020, 23:29

Catstail,

Python
1
print(isSquare([3,3,3,2],[2,3,2,2]))

должно быть False?

@isaak · 06.12.2020, 23:33

Сообщение от КулХацкеръ

read() поставь на 4 пробела ближе к левому краю (убери отступ).

От души, успехов!

@Catstail · 07.12.2020, 10:09

eaa, по-моему - да. Две точки совпадают. Но на всякий случай нулевые расстояния нужно отсечь:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from random import randint
 
def task(arr):
    x=arr[0::2]
    y=arr[1::2]
    n=len(x)
    for i in range(n-3):
        for j in range(i+1,n-2):
            for k in range(j+1,n-1):
                for p in range(k+1,n):
                    xx=[x[i],x[j],x[k],x[p]]
                    yy=[y[i],y[j],y[k],y[p]]
                    if isSquare(xx,yy):
                        print(i,j,k,p)
                        
def isSquare(x,y):
    d=[0,0,0,0,0,0]
    k=0
    for i in range(3):
        for j in range(i+1,4):
            p=x[i]-x[j]
            q=y[i]-y[j]
            d[k]=p*p+q*q
            k+=1
    if 0 in d:
        return False
    for a in d:
        if not d.count(a) in [2,4]:
            return False
    return True        
 
coords=[randint(-10,10) for i in range(100)]
task(coords)

@eaa · 07.12.2020, 10:20

Catstail, какие точки совпадают? Вроде 4 разные точки.

@Catstail · 07.12.2020, 10:27

Сообщение от eaa

[3,3,3,2],[2,3,2,2]

первая (3,2); вторая (3,3); третья (3,2) - совпадает со второй; четвертая (2,2).

@eaa · 07.12.2020, 10:43

Catstail, а, вон оно чё)) не понял как Вы задаёте точки.

Добавлено через 11 минут

Python
1
print(isSquare([2,1,2,3],[1,2,2,3]))

Вот квадрат по мнению Вашей функции.

@Catstail · 07.12.2020, 11:24

eaa, а так:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def isSquare(x,y):
    d=[0,0,0,0,0,0]
    k=0
    for i in range(3):
        for j in range(i+1,4):
            p=x[i]-x[j]
            q=y[i]-y[j]
            d[k]=p*p+q*q
            k+=1
    if len(set(d))==2:
        mi=min(d)
        ma=max(d)
        if d.count(mi)==4 and d.count(ma)==2:
            return True
    else:
        return False

@eaa · 07.12.2020, 11:49

Catstail,
вроде так нарисовал:

Новые блоги и статьи Все статьи Все блоги /
Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .	Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .
Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .	Генератор паролей (вариант №4) Maks 01.11.2026 После публикации 3-го варианта генератора паролей, разослал его своим коллегам (с целью оценки), в итоге были получены следующие рекомендации: 1. Вернуть возможность использования знаков \| 1 l I;. . .

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,320
	06.12.2020, 22:37
	Catstail, понятно - чужой "синтаксис" поправил... isaak, там четыре точки... Ну и код не мой - проверка в нем при определенных значениях "вылетает" 1

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,320
	06.12.2020, 22:41
	КулХацкеръ, но ппц и не лень же... Завидую терпению. Добавлено через 2 минуты КулХацкеръ, Можно combinations перебрать все "четверки" из N. И на проверку "отправлять" 2

@isaak 90 / 125 / 28 Регистрация: 17.10.2010 Сообщений: 1,338
	06.12.2020, 22:57
	КулХацкеръ, круто спасибо за терпение и упорство. 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,320
	06.12.2020, 23:18
	Catstail, такие решения (циклами) видел. Просто интересно, что быстрее: комбинации модулем или просто перебором в цикле? Добавлено через 1 минуту А так весь цимес этой задачи , по-моему, в функции определения квадрата 1

@КулХацкеръ 710 / 356 / 104 Регистрация: 09.02.2018 Сообщений: 805
	06.12.2020, 23:28
	У, Catstail, это интересно! В следующий вечер будет что поизучать. А сейчас уже спа-а-ать охота . Добавлено через 1 минуту isaak, read() поставь на 4 пробела ближе к левому краю (убери отступ). 1

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	07.12.2020, 10:20
	Catstail, какие точки совпадают? Вроде 4 разные точки. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	07.12.2020, 11:49
	Catstail, вроде так нарисовал: 1

Определить номера точек, которые могут являться вершинами квадрата

Решение