Задания
Версия для печати и копирования в MS Word
Тип 27 № 89210
i

Фраг­мент звёзд­но­го неба спро­еци­ро­ван на плос­кость с де­кар­то­вой си­сте­мой ко­ор­ди­нат. Учёный решил про­ве­сти кла­сте­ри­за­цию по­лу­чен­ных точек, яв­ля­ю­щих­ся изоб­ра­же­ни­я­ми звёзд, то есть раз­бить их мно­же­ство на N не­пе­ре­се­ка­ю­щих­ся не­пу­стых под­мно­жеств (кла­сте­ров), таких что точки каж­до­го под­мно­же­ства лежат внут­ри пря­мо­уголь­ни­ка со сто­ро­на­ми дли­ной H и W, причём эти пря­мо­уголь­ни­ки между собой не пе­ре­се­ка­ют­ся. Сто­ро­ны пря­мо­уголь­ни­ков не обя­за­тель­но па­рал­лель­ны ко­ор­ди­нат­ным осям.

Га­ран­ти­ру­ет­ся, что такое раз­би­е­ние су­ще­ству­ет и един­ствен­но для за­дан­ных раз­ме­ров пря­мо­уголь­ни­ков.

Га­ран­ти­ру­ет­ся, что во всех кла­сте­рах ко­ли­че­ство точек раз­лич­но.

Для каж­дой звез­ды за­да­на ха­рак­те­ри­сти­ка  — набор сим­во­лов, вклю­ча­ю­щий спек­траль­ный класс (обо­зна­ча­ет­ся ла­тин­ской бук­вой), под­класс све­ти­мо­сти (обо­зна­ча­ет­ся араб­ской циф­рой) и класс све­ти­мо­сти (обо­зна­ча­ет­ся рим­ской циф­рой).

Спек­траль­ный класс звез­ды опре­де­ля­ет­ся в со­от­вет­ствии с таб­ли­цей:

 

Спек­траль­ный класс звез­ды
OBAFGKM
Го­лу­баяБело-го­лу­баяБелаяЖёлто-белаяЖёлтаяОран­же­ваяКрас­ная

 

Класс све­ти­мо­сти звез­ды опре­де­ля­ет­ся в со­от­вет­ствии с таб­ли­цей:

 

Класс све­ти­мо­сти звез­ды
IIIIIIIVVVIVII
сверх­ги­гантяркий ги­гантги­гантсуб­ги­ганткар­ликсуб­кар­ликква­зар

 

Будем на­зы­вать цен­тром кла­сте­ра точку этого кла­сте­ра, сумма рас­сто­я­ний от ко­то­рой до всех осталь­ных точек кла­сте­ра ми­ни­маль­на. Для каж­до­го кла­сте­ра га­ран­ти­ру­ет­ся един­ствен­ность его цен­тра. Рас­сто­я­ние между двумя точ­ка­ми на плос­ко­сти А(х1, y1) и B(х2, y2) вы­чис­ля­ет­ся по фор­му­ле:

d левая круг­лая скоб­ка A, B пра­вая круг­лая скоб­ка = ко­рень из: на­ча­ло ар­гу­мен­та: левая круг­лая скоб­ка x_2 минус x_1 пра­вая круг­лая скоб­ка в квад­ра­те плюс левая круг­лая скоб­ка y_2 минус y_1 пра­вая круг­лая скоб­ка в квад­ра­те конец ар­гу­мен­та .

В файле А хра­нят­ся дан­ные о звёздах двух кла­сте­ров, где Н  =  5 и W  =  4 для каж­до­го кла­сте­ра. В каж­дой стро­ке за­пи­са­на ин­фор­ма­ция одной звез­ды: ко­ор­ди­на­та х, ко­ор­ди­на­та у и её ха­рак­те­ри­сти­ка. Зна­че­ния даны в услов­ных еди­ни­цах. Из­вест­но, что ко­ли­че­ство точек не пре­вы­ша­ет 1000.

В файле Б хра­нят­ся дан­ные о звёздах трёх кла­сте­ров, где Н  =  3 и W  =  5 для каж­до­го кла­сте­ра. Из­вест­но, что ко­ли­че­ство точек не пре­вы­ша­ет 10 000.

Струк­ту­ра хра­не­ния ин­фор­ма­ции о звёздах в файле Б ана­ло­гич­на струк­ту­ре в файле А.

Файл А

Файл Б

Для файла А опре­де­ли­те ко­ор­ди­на­ты цен­тра каж­до­го кла­сте­ра, затем най­ди­те два числа: A1  — абс­цис­су бли­жай­ше­го бе­ло­го ги­ган­та к цен­тру кла­сте­ра с наи­мень­шим ко­ли­че­ством точек, и A2  — ор­ди­на­ту бли­жай­ше­го бе­ло­го ги­ган­та к цен­тру кла­сте­ра с наи­мень­шим ко­ли­че­ством точек.

Для файла Б опре­де­ли­те ко­ор­ди­на­ты цен­тра каж­до­го кла­сте­ра, затем най­ди­те два числа: B1  — рас­сто­я­ние между цен­тра­ми кла­сте­ров с наи­боль­шим и наи­мень­шим ко­ли­че­ством крас­ных сверх­ги­ган­тов, и B2  — мак­си­маль­ное рас­сто­я­ние между двумя жёлтыми кар­ли­ка­ми, на­хо­дя­щи­ми­ся в одном кла­сте­ре.

В от­ве­те за­пи­ши­те че­ты­ре числа: в пер­вой стро­ке  — сна­ча­ла целую часть про­из­ве­де­ния A1 × 10 000, затем целую часть про­из­ве­де­ния A2 × 10 000; во вто­рой стро­ке  — сна­ча­ла целую часть про­из­ве­де­ния B1 × 10 000, затем целую часть про­из­ве­де­ния B2 × 10 000.

 

Ответ:

Спрятать решение

Ре­ше­ние.

По­стро­им диа­грам­му для файла А и В. Для этого от­кро­ем файлы с по­мо­щью python.

Гра­фик для файла А:

Гра­фик для файла В:

 

При­ведём ре­ше­ние для файла А и B на языке Python.

import tkinter as tk

import math

all_stars = []

with open('27_B.txt') as f:

for line in f:

line = line.replace(',', '.').strip()

parts = line.split()

# Чи­та­ем ко­ор­ди­на­ты и тип

raw_x = float(parts[0])

raw_y = float(parts[1])

info = parts[2]

all_stars.append((raw_x, raw_y, info))

#На­хо­дим экс­тре­му­мы для жест­ко­го мас­шта­би­ро­ва­ния

if all_stars:

xs = [s[0] for s in all_stars]

ys = [s[1] for s in all_stars]

min_x, max_x = min(xs), max(xs)

min_y, max_y = min(ys), max(ys)

# За­да­ем фик­си­ро­ван­ный раз­мер окна

W, H = 1000, 700

pad = 50 # От­ступ от краев, чтобы точки не при­ли­па­ли к рамке

# За­щи­та от де­ле­ния на ноль, если все ко­ор­ди­на­ты оди­на­ко­вые

dx = (max_x - min_x) if max_x != min_x else 1

dy = (max_y - min_y) if max_y != min_y else 1

# Рас­счи­ты­ва­ем SCALE

SCALE_X = (W - 2 * pad) / dx

SCALE_Y = (H - 2 * pad) / dy

SCALE = min(SCALE_X, SCALE_Y)

print(f"[+] Гра­ни­цы дан­ных: X от {min_x} до {max_x}, Y от {min_y} до {max_y}")

print(f"[+] Вы­чис­лен­ный мас­штаб от­ри­сов­ки (SCALE): {round(SCALE, 4)}")

else:

min_x, min_y, SCALE, pad, W, H = 0, 0, 1, 50, 1000, 700

# Пе­ре­вод в пик­се­ли

def to_px(rx, ry):

px = (rx - min_x) * SCALE + pad

py = H - ((ry - min_y) * SCALE + pad) # Ин­вер­сия Y для нор­маль­ной де­кар­то­вой сетки

return px, py

# Клик-об­ра­бот­чик

def click_handler(event):

if not all_stars: return

# Пе­ре­во­дим пик­се­ли клика об­рат­но в ма­те­ма­ти­ку файла

cx = min_x + (event.x - pad) / SCALE

cy = min_y + (H - event.y - pad) / SCALE

closest = None

min_d = float('inf')

for star in all_stars:

rx, ry, info = star

d = math.hypot(cx - rx, cy - ry)

if d < min_d:

min_d = d

closest = star

rx, ry, info = closest

print(f"+ Клик мыш­кой по экра­ну в пик­се­лях: ({event.x}, {event.y})")

print(f"* Бли­жай­шая к клику ре­аль­ная звез­да: X = {rx}, Y = {ry}, Тип = {info}")

print("-" * 50)

# 3. Гра­фи­че­ский ин­тер­фейс Tkinter

root = tk.Tk()

root.title("Кли­кер Кла­сте­ров")

canvas = tk.Canvas(root, width=W, height=H, bg='black')

canvas.pack()

canvas.bind("<1>", click_handler)

# От­ри­сов­ка

for rx, ry, info in all_stars:

px, py = to_px(rx, ry)

color = 0

#print(info[0], info[2:])

# Цве­то­вая под­свет­ка

if 'A' == info[0] and 'III' == info[2:]:

color = 'white'

elif 'M' == info[0] and 'I' == info[2:]:

color = 'red'

elif 'G' == info[0] and 'V' == info[2:]:

color = 'yellow'

# Можно те­гать для удоб­ства уби­рая лиш­ние звёзды

else:

color = '#444444' # Обыч­ные серые фо­но­вые звез­ды

# Ри­су­ем жир­ные, за­мет­ные квад­ра­ты 2х2 пик­се­ля

if color:

canvas.create_rectangle(px-1, py-1, px+1, py+1, fill=color, outline=color)

# Для файла A

#border_y = 35

#cluster_1 = [s for s in all_stars if s[1] < border_y]

#cluster_2 = [s for s in all_stars if s[1] > border_y]

#target_cluster = cluster_1 if len(cluster_1) < len(cluster_2) else cluster_2

# Для файла B

cluster_1 = [s for s in all_stars if 7 < s[1] < 12.5]

cluster_2 = [s for s in all_stars if s[1] < 7]

def best_centroid(target_cluster):

best_center = None

min_sum = float('inf')

for cx, cy, _ in target_cluster:

curr_sum = sum(math.hypot(cx - px, cy - py) for px, py, _ in target_cluster)

if curr_sum < min_sum:

min_sum = curr_sum

best_center = (cx, cy)

print(best_center)

# Для файла A

#best_centroid(target_cluster)

# От­ве­ты A1 и A2

#print(int(39.02054737781699 * 10**4))

#print(int(18.269948438629243 * 10**4))

 

# Для файла B

best_centroid(cluster_1), best_centroid(cluster_2)

# От­ве­ты B1 и B2

print(int(((abs( 23.55819983673737 - 22.298551302558078))**2 + (abs(11.207801969160332 - 5.310152626026702))**2)**0.5 * 10**4))

print(int(((abs(22.32521100897972 - 23.194249781245507))**2 + (abs(16.329963528862102 - 17.72793552467998))**2)**0.5 * 10**4))

root.mainloop()

 

 

Ответ: 390205 182699 60306 16460.


Аналоги к заданию № 89210: 89246 Все