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

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

ただいまの
回答率

90.52%

  • Python

    7938questions

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

  • Python 3.x

    6348questions

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

  • Python 2.7

    1259questions

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

円内にある点を集計する

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 179

yositigu

score 8

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を想定

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • 退会済みユーザー

    2018/06/12 15:56

    複数のユーザーから「やってほしいことだけを記載した丸投げの質問」という意見がありました
    「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

  • yuba

    2018/06/12 16:28

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

    キャンセル

  • yositigu

    2018/06/12 16:58

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

    キャンセル

回答 1

checkベストアンサー

+1

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

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

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

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

from random import random

r = 5.0
ew = 5000.0
ns = 5000.0
phone_count = 1000000
site_count = 1000


def test_data():
    # 電話機の座標を 1000000個
    phones = {(random() * ew, random() * ns) for _ in range(phone_count)}

    # 基地局候補値の座標を 1000個
    sites = {(random() * ew, random() * ns) for _ in range(site_count)}

    return phones, sites


def map_phones(phones):
    """
    5キロ区切りのマス目に電話機を割り振る
    """
    phones_map = {}
    for phone in phones:
        x, y = phone
        bucket = (int(x / r), int(y / r))
        if bucket in phones_map:
            phones_map[bucket].add(phone)
        else:
            phones_map[bucket] = {phone}
    return phones_map


def covering_phones(phones_map, site):
    """
    候補地がカバーする電話機
    """
    x, y = site
    site_bucket = (int(x / r), int(y / r))

    for dx in range(-1, 2):
        for dy in range(-1, 2):
            bucket = (site_bucket[0] + dx, site_bucket[1] + dy)
            for phone in phones_map.get(bucket, set()):
                phone_x, phone_y = phone
                if (x - phone_x)**2 + (y - phone_y)**2 <= r**2:
                    yield phone


def remove_phones(phones_map, phones):
    """
    マス目マップから携帯電話を一括削除
    """
    for bucket, content in phones_map.items():
        content.difference_update(phones)


def enumerate_covering_site(phones, sites):
    """
    カバーできる電話機の数が多い順に基地局候補値と収容される電話機を返していきます
    """

    phones_map = map_phones(phones)

    while phones or sites:
        greatest_site = None
        max_covered_phones = set()

        for site in sites:
            covered_phones = set(covering_phones(phones_map, site))
            if len(covered_phones) >= len(max_covered_phones):
                greatest_site = site
                max_covered_phones = covered_phones

        yield greatest_site, max_covered_phones

        sites.remove(greatest_site)
        remove_phones(phones_map, max_covered_phones)
        phones.difference_update(max_covered_phones)


def main():
    phones, sites = test_data()
    for site, covered_phones in enumerate_covering_site(phones, sites):
        print(site)
        print(covered_phones)


main()

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

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

  • ただいまの回答率 90.52%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 受付中

    神経衰弱のコード

    以下の内容をコードに組み込みたいのですが、どうすればよいのか分からず質問させていただきます。 「トランプカードの52枚からランダムで数字が同じ8ペア(16枚)が自動で選択され画面上

  • 解決済

    unity 画面内に同じものを表示しない

    unityでランダムでキャラクターを表示していくものなのですが、画面内に同じキャラクターが表示されてしまうのでされないようにしたいです。 キャラクターは一定時間でCloneされ一

  • 解決済

    チェックしているつもりがNullPointerException

    抜粋の中の以下の行でNullPointerExceptionが発生してしまいます。 きちんとwhile 文でチェックしているはずですが、なぜでしょうか。 random_nu

  • 解決済

    インターネット上で利用できる unique id に関して

    Webアプリ制作中なのですが、インターネット上で利用できる unique な id を作成する方法を探しています。 RFC4122 を参考にすると、時間 + 端末固有の識別番

  • 解決済

    【unity】2回目のfor文でunityがフリーズしてしまう

    前提・実現したいこと 5個のオブジェクトを全て違う位置に一気に表示し、そのオブジェクトが消えたらまた同じように表示するという処理をfor文で書いたのですが、2回目のfor文でフリー

  • 解決済

    乱数を重複なく複数回表示したい

    前提・実現したいこと 現在unity5.6.1で落ちもの型のパズルゲームを作成しています。 7種類のブロックをランダムに重複なく一つずつ生成し7種類すべて生成したら、またランダムに

  • 解決済

    条件付きの乱数の作り方を質問させてください

    条件付きの乱数の作り方を質問させてください。 スマホのパズルゲームを製作しております。(初心者、unity5.6使用) 10ピースのパズルがあり、 ゲーム開始時に、パズルピース

  • 解決済

    文字列の配列を、重複なしで乱数にするには

     前提・実現したいこと C#とUnityで現在クイズゲームを作っています。クイズの問題を、一度解いたものが出ないように、ランダムで出したいと思っています。  発生している問題・

同じタグがついた質問を見る

  • Python

    7938questions

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

  • Python 3.x

    6348questions

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

  • Python 2.7

    1259questions

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