質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Python 2.7

Python 2.7は2.xシリーズでは最後のメジャーバージョンです。Python3.1にある機能の多くが含まれています。

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

1回答

2147閲覧

円内にある点を集計する

yositigu

総合スコア17

Python 2.7

Python 2.7は2.xシリーズでは最後のメジャーバージョンです。Python3.1にある機能の多くが含まれています。

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2018/06/12 06:44

編集2018/06/12 07:57

python3で下記の処理を教えてください.

入力①:ランダムな点の座標(x,y)リストA
入力②:円を置くことができる座標(p.q)リストB
入力③:円の半径 r

Bで与えられた位置座標に円をそれぞれ置いた時に、どの位置座標に置いた時一番多くAの点をカバーできるか判定

出力:一番Aの点を多くカバーできるBの位置座標
出力2:一番Aの点を多くカバーできるBの位置座標に置いた時にカバーされる点のリスト

これが完了後、カバーされる点を除いて同様の処理をloopしたいと思います。

入力サイズのざっくりイメージ
入力①:ランダムな点の座標(x,y)リストA: 10万~100万を想定
入力②:円を置くことができる座標(p.q)リストB : 1000個を想定
入力③:円の半径 r : 5kmを想定

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

yuba

2018/06/12 07:28

何かの授業課題かプログラミングコンテストの問題とお見受けします。座標リストのサイズによって考え方が変わってきます。数百個×数百個とかなら特に工夫することはありません。こうして質問を立てておられるからには数万個×数万個のオーダーだということでしょうか。というわけで入力サイズと制限時間も回答に必要な情報です。
yositigu

2018/06/12 07:58

入力サイズを記載させていただきました。授業の課題等ではなく、自由研究になります。
guest

回答1

0

ベストアンサー

携帯基地局や公共施設の配置最適化の問題っぽい話ですね。
(一瞬、水着画像を水玉コラに加工するのの自動化? と思いましたがそれだと逆ですか)

ここでは便宜的に、Aの要素を携帯電話、Bの要素を基地局候補値と呼ぶことにします。

実用的な速度で実現するヒントとしては
・地図全体を5キロ区切りのマス目に区切り、携帯電話を該当するマス目に所属させます。
・基地局候補値から5キロ以内という判定対象は、周囲9マスの所属携帯電話だけに限定できます。

このアイディアをプログラムにするとこんな感じですかね。

python

1from random import random 2 3r = 5.0 4ew = 5000.0 5ns = 5000.0 6phone_count = 1000000 7site_count = 1000 8 9 10def test_data(): 11 # 電話機の座標を 1000000個 12 phones = {(random() * ew, random() * ns) for _ in range(phone_count)} 13 14 # 基地局候補値の座標を 1000個 15 sites = {(random() * ew, random() * ns) for _ in range(site_count)} 16 17 return phones, sites 18 19 20def map_phones(phones): 21 """ 22 5キロ区切りのマス目に電話機を割り振る 23 """ 24 phones_map = {} 25 for phone in phones: 26 x, y = phone 27 bucket = (int(x / r), int(y / r)) 28 if bucket in phones_map: 29 phones_map[bucket].add(phone) 30 else: 31 phones_map[bucket] = {phone} 32 return phones_map 33 34 35def covering_phones(phones_map, site): 36 """ 37 候補地がカバーする電話機 38 """ 39 x, y = site 40 site_bucket = (int(x / r), int(y / r)) 41 42 for dx in range(-1, 2): 43 for dy in range(-1, 2): 44 bucket = (site_bucket[0] + dx, site_bucket[1] + dy) 45 for phone in phones_map.get(bucket, set()): 46 phone_x, phone_y = phone 47 if (x - phone_x)**2 + (y - phone_y)**2 <= r**2: 48 yield phone 49 50 51def remove_phones(phones_map, phones): 52 """ 53 マス目マップから携帯電話を一括削除 54 """ 55 for bucket, content in phones_map.items(): 56 content.difference_update(phones) 57 58 59def enumerate_covering_site(phones, sites): 60 """ 61 カバーできる電話機の数が多い順に基地局候補値と収容される電話機を返していきます 62 """ 63 64 phones_map = map_phones(phones) 65 66 while phones or sites: 67 greatest_site = None 68 max_covered_phones = set() 69 70 for site in sites: 71 covered_phones = set(covering_phones(phones_map, site)) 72 if len(covered_phones) >= len(max_covered_phones): 73 greatest_site = site 74 max_covered_phones = covered_phones 75 76 yield greatest_site, max_covered_phones 77 78 sites.remove(greatest_site) 79 remove_phones(phones_map, max_covered_phones) 80 phones.difference_update(max_covered_phones) 81 82 83def main(): 84 phones, sites = test_data() 85 for site, covered_phones in enumerate_covering_site(phones, sites): 86 print(site) 87 print(covered_phones) 88 89 90main()

投稿2018/06/12 13:31

yuba

総合スコア5568

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問