数学
173:デフォルトの名無しさん 2015/05/23(土) 12:50:18.11 ID:PpO+s1up.net

お題
平面上の点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)の値を求めよ。


スポンサードリンク
174:デフォルトの名無しさん 2015/05/23(土) 13:37:10.47 ID:TCe7XEwZ.net

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


175:デフォルトの名無しさん 2015/05/23(土) 14:05:35.40 ID:CdB4mnZs.net

ショボーン


176:デフォルトの名無しさん 2015/05/23(土) 18:41:03.49 ID:KLESbJHw.net

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

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


177:デフォルトの名無しさん 2015/05/23(土) 19:41:48.57 ID:xvr22N4V.net

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


178:デフォルトの名無しさん 2015/05/23(土) 20:04:53.12 ID:1SFlVJvM.net

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


179:デフォルトの名無しさん 2015/05/23(土) 20:17:17.58 ID:1SFlVJvM.net

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


180:デフォルトの名無しさん 2015/05/23(土) 21:17:24.86 ID:xvr22N4V.net

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


181:デフォルトの名無しさん 2015/05/23(土) 21:34:54.34 ID:1SFlVJvM.net

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


183:デフォルトの名無しさん 2015/05/24(日) 01:09:29.39 ID:neLU6sWs.net

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


184:デフォルトの名無しさん 2015/05/24(日) 01:19:01.88 ID:I/ZOM1+g.net

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


185:デフォルトの名無しさん 2015/05/24(日) 02:42:51.04 ID:neLU6sWs.net

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


186:デフォルトの名無しさん 2015/05/24(日) 02:44:54.66 ID:neLU6sWs.net

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


189:デフォルトの名無しさん 2015/05/24(日) 16:41:09.92 ID:+Ut0g5Td.net

>>173
Io


f := method(p, 
 line := list 
 for(i, 0, p size - 2, 
  x1 := p at(i) at(0); y1 := p at(i) at(1) 
  for(j, i + 1, p size - 1, 
   x2 := p at(j) at(0); y2 := p at(j) at(1) 
   a := x2 - x1; b := y2 - y1 
   c := (x2 * x2 + y2 * y2 - x1 * x1 - y1 * y1) / 2 
   d := (a * a + b * b) sqrt 
   line push(list(a / d, b / d, c / d)) 
  ) 
 ) 
 line uniqueCount map(last) max * 2 
)

187:デフォルトの名無しさん 2015/05/24(日) 03:28:30.16 ID:RlzRxNiR.net

>>173
C++

max(N(L)) = 3
例えば、 (4, 2) と (8, 2) がLに対して線対称です。

188:187 2015/05/24(日) 05:16:24.96 ID:RlzRxNiR.net

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


元スレ:http://toro.2ch.sc/test/read.cgi/tech/1429195275/