他サイト更新RSSぴぽぺ速報最新記事

平面上の点v[n]が与えられる、一本の直線で折って重ねることができる点の個数の最大値を求めよ

このエントリーをはてなブックマークに追加 LINEで送る

お題
平面上の点v[1],...,v[n]が与えられる。
一本の直線で折って重ねることができる点の個数の最大値を求めよ。

より正確には、直線Lに対して、Lで折ることで点v[i]が移る先の点をL(v[i]) とおき、L(v[i])∈{v[1],...,v[n]}となるような点v[i]の個数をN(L)とおくとき、 N(L)が最大となるような直線Lを探し、そのときのN(L)の値を求めよ。

まったく解法の見当もつかんw

ショボーン

O(n^2)はすぐ思いつくけど、計算量が厳しそうだな・・・

補足:アルゴリズム計算量のこと

愚直に2点の全パターンを試すO(n^3)しか思いつかない自分にO(n^2)の解法を教えてくり

枠が有限の折り紙としてもいいんだろ。
異なる二線分を選び、追ってみればできるか?
線分が重複しないケースもあるか? すくなくとも2点重なれば線分がかさなるか。

2点から等距離にある直線にしたらO(n*n)か。

>>179 直線の数がn^2でそれぞれN(L)求めるのにnかかるからn^3では

検証するのにO(n)かかるってことか。
直線候補の抽出がO(n)で可能ってほんとかよ?

数学はわからんつってるだろ。(逆切れ。

数学といっても中学レベルだろ?
小学生だったらいいが。
中学以上なのに理解できないとなるとヤバイのでは。

題意を理解するのに10分以上かかる底辺なめんなよ。(さらに逆切れ)

一応考えかた考えてみたけど、外側の点を洗い出して平行四辺形での中線を折ることを考えるとよさそうだとは思った。
数学怖い。

>>173
Io

>>173
C++

答えの計算間違えた
3じゃなくて8だ

sosu



このエントリーをはてなブックマークに追加 LINEで送る
↑この記事をみんなに広めよう↑

↓ランキングクリックよろしくお願いします↓
 にほんブログ村 2ちゃんねるブログ 2ちゃんねる(ニュース)へ にほんブログ村 2ちゃんねるブログ 2ちゃんねる(ゲーム)へ

コメントをどうぞ

メールアドレス
コメント本文

  • あなたのコメントが、更にこの記事をおもしろくします。

プロフィール

PipopeFavicon

ぴぽぺ速報です。

下らないニュース、
おもしろい事件、
ゲームなど色々扱っております。
1日約70記事です。

Twitter
RSS

↓ランキングクリックよろしくお願いします↓
 にほんブログ村 2ちゃんねるブログ 2ちゃんねる(ニュース)へ にほんブログ村 2ちゃんねるブログ 2ちゃんねる(ゲーム)へ

新着情報

逆アクセスランキング

アクセスカウンター

  • 20現在の記事:
  • 1544885総閲覧数:
  • 75今日の閲覧数:
  • 395昨日の閲覧数:
  • 555082総訪問者数:
  • 33今日の訪問者数:
  • 145昨日の訪問者数:
  • 165一日あたりの訪問者数:
  • 0現在オンライン中の人数:

genzou1919 world