プログラミングのお題スレ Part14

**デフォルトの名無しさん** · 2019/05/18(土) 17:33:29.45

プログラミングのお題スレです。

【出題と回答例】
1 名前：デフォルトの名無しさん
　　お題：お題本文

2 名前：デフォルトの名無しさん
　　>>1 使用言語
　　回答本文
　　結果がある場合はそれも

【ソースコードが長くなったら】 (オンラインでコードを実行できる)
https://ideone.com/
http://codepad.org/
http://compileonline.com/
http://rextester.com/runcode
https://runnable.com/
https://code.hackerearth.com/
http://melpon.org/wandbox
https://paiza.io/

宿題は宿題スレがあるのでそちらへ。

※前スレ
https://mevius.5ch.net/test/read.cgi/tech/1549160513/

**デフォルトの名無しさん** · 2019/05/19(日) 20:20:05.14

>>9
Haskell

import Data.Char

main = (print.sumnum) 12

sumnum 0 = [0]
sumnum n |n < 0 = error "Please n >= 0 number"
sumnum n = take 5 [x | x <- [0..], n == sum [read [a]| a <- show x]]

**デフォルトの名無しさん** · 2019/05/19(日) 20:25:29.07

>>5
Java
https://paiza.io/projects/lPsVtvM3yO0cQEnRxg7fpQ

◆QZaw55cn4c · 2019/05/19(日) 20:30:36.06

>>36
いいことを教えてもらいました、Java って uft-16 だけかとおもっていました…

**デフォルトの名無しさん** · 2019/05/19(日) 21:30:05.06

>>33
組み込みメソッドの使用禁止とかばかげてる

◆QZaw55cn4c · 2019/05/19(日) 21:53:11.12

https://mevius.5ch.net/test/read.cgi/tech/1549160513/779
https://mevius.5ch.net/test/read.cgi/tech/1434079972/57

**デフォルトの名無しさん** · 2019/05/19(日) 22:17:12.44

出禁 ID:8BTe2vpb

**デフォルトの名無しさん** · 2019/05/19(日) 22:26:04.27

正直言ってここに出てくるお題よりAtCoderのお題の方がレベル高いよね

**デフォルトの名無しさん** · 2019/05/19(日) 22:53:21.34

11がマジで難しいんだけど、だれか取り組んでる？

◆QZaw55cn4c · 2019/05/20(月) 00:00:59.23

>>41
小ネタの合間にめんどくさいものがポツポツあるかと　>>11 とか

**デフォルトの名無しさん** · 2019/05/20(月) 02:35:31.92

>>5
Kotlin
https://paiza.io/projects/DCRebTKGifCuLe5ysI1JIA

**デフォルトの名無しさん** · 2019/05/20(月) 06:02:09.58

漏れなんて、書き捨てのRuby のファイルが、100もある

いつも、Windows10 で、WSL, Ubuntu16.04 から、grep してる

**デフォルトの名無しさん** · 2019/05/20(月) 06:44:50.41

お、ツッコミ待ちか？

**デフォルトの名無しさん** · 2019/05/20(月) 07:53:09.19

お題
Excelのカラム名でHELLOからWORLDまで表示する

**デフォルトの名無しさん** · 2019/05/20(月) 09:16:55.34

>>11 問題1の斜めにしない直行正方形までは出た。

xの範囲= (94, 31) (850, 598) 差 756
yの範囲= (94, 31) (110, 927) 差 896
1辺= 896

直行正方形 (94, 31) (990, 31) (94, 927) (990, 927)
次はこれを傾けていくんだな。これがムズイ。

**デフォルトの名無しさん** · 2019/05/20(月) 13:11:43.52

>>11 x,y座標は　０～999までの整数　辺の長さは斜めになった時は整数とは限らない。

**デフォルトの名無しさん** · 2019/05/20(月) 15:10:01.16

プログラミングのお題スレ Part13
https://mevius.5ch.net/test/read.cgi/tech/1549160513/920-984

前スレのランク付けの問題は、O(n^2)とかなら簡単なんだが、
ハッシュなどを使って、計算回数を少なくするのに、苦戦してる

入力データ
-6 3 9 5 3 -7
出力・ランク
2 3 5 4 3 1

**デフォルトの名無しさん** · 2019/05/20(月) 18:09:47.07

ハッシュを使ってんのがperlのじゃねえの

**デフォルトの名無しさん** · 2019/05/20(月) 19:35:06.91

ランク付けならmap使うと楽、O(NlogN)が想定解

**デフォルトの名無しさん** · 2019/05/20(月) 19:41:12.77

前スレの場合、みんなハッシュ(set)かソート使ってたじゃん

**デフォルトの名無しさん** · 2019/05/20(月) 19:53:28.74

>>53 コンパクトなコーディングはみんなほぼ同じだったね。

python smalltalk java

なんかプログラミング言語を見直しはじめたよ。
複雑にせずに根本を見つめるコーディングが出来る言語というのは素晴らしい。

**デフォルトの名無しさん** · 2019/05/20(月) 19:56:03.94

え、JAVA?

**デフォルトの名無しさん** · 2019/05/20(月) 19:58:48.02

>>前ｽﾚ988 Perl5
https://mevius.5ch.net/test/read.cgi/tech/1549160513/988

sub p {
　$h = int $n/2;
　for ($i=2; $i<=$h; $i++) {
　　$s[$i] = 1 unless exists $s[$i];
　　do {$s[$i*$_] = 0 for 2..int $h/$i} if $s[$i];
　}
　@p = grep{$s[$_]} 2..$h;
}
sub f {
　my $i = shift;
　my $h = int $i/2;
　for $j (grep{$_ <= $h} @p) {
　　return ($j, f($i/$j)) if 0 == $i % $j;
　}
　$i
}
for $n (qw{28 2002 216653}) {
　p;
　my %f; $f{$_}++ for f($n);
　@f = map{$_ . (1 < $f{$_} and "^$f{$_}")} sort{$a<=>$b} keys %f;
　$" = '+';
　print "$n => @f\n";
}

実行
~ $ perl 13_988.pl
28 => 2^2+7
2002 => 2+7+11+13
216653 => 216653

**デフォルトの名無しさん** · 2019/05/20(月) 20:01:05.70

setにぶちこんで重複削除、リストにしてソートしてマップの値の方にインデックス入れて最後にそのマップ使って出して完成

**デフォルトの名無しさん** · 2019/05/20(月) 20:02:09.53

ゆっくり書いてたら間にたくさんの書き込みが入った。
俺のことは忘れてくれ。

**デフォルトの名無しさん** · 2019/05/20(月) 20:08:45.44

>>56 ｽﾏｿ、ｹｱﾚｽミスった、繋ぐ演算子は+ => *だた…orz
sub p {
　$h = int $n/2;
　for ($i=2; $i<=$h; $i++) {
　　$s[$i] = 1 unless exists $s[$i];
　　do {$s[$i*$_] = 0 for 2..int $h/$i} if $s[$i];
　}
　@p = grep{$s[$_]} 2..$h;
}
sub f {
　my $i = shift;
　my $h = int $i/2;
　for $j (grep{$_ <= $h} @p) {
　　return ($j,f($i/$j)) if 0 == $i % $j;
　}
　$i
}
for $n (qw{28 2002 216653}) {
　p;
　my %f; $f{$_}++ for f($n);
　@f = map{$_ . (1 < $f{$_} and "^$f{$_}")} sort{$a<=>$b} keys %f;
　$" = '*';
　print "$n => @f\n";
}

実行
~ $ perl 13_988.pl
28 => 2^2*7
2002 => 2*7*11*13
216653 => 216653

◆QZaw55cn4c · 2019/05/21(火) 22:06:24.96

test

◆QZaw55cn4c · 2019/05/21(火) 22:14:40.60

>>56
https://mevius.5ch.net/test/read.cgi/tech/1434079972/58

◆QZaw55cn4c · 2019/05/21(火) 22:17:32.24

お題と回答
>>5 : 6 10 32 36 44
>>9 : 15 34 35
>>11 : 48
>>19 :
>>50, https://mevius.5ch.net/test/read.cgi/tech/1549160513/920 :
https://mevius.5ch.net/test/read.cgi/tech/1549160513/988 : 59 61

**デフォルトの名無しさん** · 2019/05/21(火) 23:09:46.41

あなたが解けない C/C++/Java/C#/JavaScript の問題を有償で片付けるスレッドです

**デフォルトの名無しさん** · 2019/05/21(火) 23:10:51.22

有償で片付けるスレッドに貼り付けるのはよろしくないね
有償で片付けてほしくて出題してるわけじゃないでしょ
問題の窃盗だよ

**デフォルトの名無しさん** · 2019/05/21(火) 23:21:22.29

>>59
Perlは配列に対するexistsやdefinedは呼び出せるが振る舞いは不明確で「強く」非推奨となっているので
この場合では問題なくとも@pはリストではなく代わりにハッシュ%pを使って実装するべきだった

**デフォルトの名無しさん** · 2019/05/21(火) 23:33:57.22

>>65
ハッシュにしたほうが良いのは@pじゃなくて@sの方だったわ

**デフォルトの名無しさん** · 2019/05/21(火) 23:56:06.27

>>64
バカチョンには何を言っても無駄だと思うよ
聞く耳持たない分からず屋の馬鹿だからバカチョンなんだから

**デフォルトの名無しさん** · 2019/05/22(水) 00:03:24.91

>>64
>>27に理由が書かれていたが、一ヶ所に纏めておくと便利だなんてのは個人の都合であって、他の人にはわざわざ間接参照を強いることになるのだから、ほんとに身勝手な奴だと思う。

>>27
纏めておくのは他所で勝手にやれ、このスレにはコードだけを貼れよ。お前の手間なぞ知ったことではない。

**デフォルトの名無しさん** · 2019/05/22(水) 00:04:37.78

ネトウヨもコテハンもうぜえわ

**デフォルトの名無しさん** · 2019/05/22(水) 01:11:55.55

>>62 折角まとめるんなら、回答の方も >> でリンクを貼って欲しいな。

**デフォルトの名無しさん** · 2019/05/22(水) 01:20:05.57

>>70
それは絶対にやらないんじゃね
奴は自分のことしか考えてないから
だから自己愛
永遠に人から煙たがられる存在

**デフォルトの名無しさん** · 2019/05/22(水) 01:29:50.95

>>11 は、多角形の中のドットの内外判定問題と言うのが確立されてるみたいね。
色んな方法があるみたいだが、簡単なのは、
Crossing Number Algorithm
らしい、ググってみると結構コンパクトなコード。
他も見てみたが、問題は境界線上にある点は多角形外と判定する事。

だから、そのままのロジックに手を入れないとした場合、使う側としてどう解決したら良いんだろう。
直行正方形を1ドットずつ大きくしてから回転させる？

それとも、多角形の中の多角形問題の方が適してるのかな？

この問題は結構勉強になる。問題のイメージを掴むために、図形表示までやり始めたよ。表示するとより楽しくなる。

**デフォルトの名無しさん** · 2019/05/22(水) 01:32:14.02

>>71 そこまで悪い人間では無さそうだけどな、おだてれば猿も木に登るタイプだとみた。
高い木に登ってもらおう。

**デフォルトの名無しさん** · 2019/05/22(水) 01:33:07.52

ｸﾞｸﾞﾗないで考えようとしていたけど、
ヒントを目にしてしまった気分
いやべつにいいけどさ

**デフォルトの名無しさん** · 2019/05/22(水) 01:34:42.74

Q. クソ問題とは何ですか？
A. 問題の解釈を巡って議論や煽り合いが10レス以上続く、バカが投稿した不備のある問題のことです。

**デフォルトの名無しさん** · 2019/05/22(水) 04:38:05.31

>>47 Ruby
("HELLO".."WORLD").each{|v| puts v}

**デフォルトの名無しさん** · 2019/05/22(水) 07:31:41.79

>>62
前スレ920 >>4

**デフォルトの名無しさん** · 2019/05/22(水) 07:39:53.22

>>72
https://dotup.org/uploda/dotup.org1853571.cpp.html

とりあえず図形表示。
一応内部の点は除去して、凸包を表示するような感じにしてる。
左クリックで頂点追加、右クリックで全削除、中クリックでリセット

操作しながらいろいろ検討してるけど、さっぱり思いつかない。

**デフォルトの名無しさん** · 2019/05/22(水) 10:43:49.16

>>9 Ruby

def sumnum(n)
(0..4).map{|i| ("1"*n +"0"*i).to_i}
end

**デフォルトの名無しさん** · 2019/05/22(水) 12:02:59.73

>>78 　
Windows じゃないと動かないようだけど見やすいようにideonに張ってみた。
https://ideone.com/gJVREH

凸包と言うんだね。

2次元の凸包を求めるアルゴリズムと応用について
https://matsu7874.hatenablog.com/entry/2018/12/17/025713
凸包(convex hull)とは，与えられた点をすべて包含する最小の凸多角形（凸多面体）のこと.

--------
凸包が求められても難しいね。　凸包内の点を削除して計算時間を削減できる効果はあるかもしれないけど。

**デフォルトの名無しさん** · 2019/05/22(水) 12:11:47.61

凸包が求められれば、頂点の並びも整列するので
形状を分割して余弦定理とかから導けないかなって思ったんだよね

**デフォルトの名無しさん** · 2019/05/22(水) 12:13:57.61

>>47
画面の幅が足りなくて表示できません。

**デフォルトの名無しさん** · 2019/05/22(水) 12:34:28.61

ちなみに、最小を求めるだけならある角度から見た凸包の一次元への投影と、直交する角度からの一次元への投影を１８０度回しながら調べれば出せると思うけど、分割の粒度の問題で、本当に最小が取れる保証はないね

**デフォルトの名無しさん** · 2019/05/22(水) 13:45:45.60

>>76
試しに Perl でも文字列 .. 文字列をやってみたらできたよ。
こんなことできたとは。知らないまま20年以上使ってたよ。w

50 · 2019/05/22(水) 19:14:59.08

>前スレの920
頭を使った。Ruby で、

str = "-6 3 9 5 3 -7"

original_ary = str.split.map!( &:to_i ) # 各要素は整数型
hash = original_ary.each_with_object( { } ) { | num, h | h[ num ] = true }

sorted_ary = hash.sort # キーでソートする
#=> [[-7, true], [-6, true], [3, true], [5, true], [9, true]]

# Enumerator#with_index(offset = 0)
sorted_hash = sorted_ary.each.with_index( 1 ) { | elem, idx | elem[ 1 ] = idx }.to_h

# p sorted_ary
#=> [[-7, 1], [-6, 2], [3, 3], [5, 4], [9, 5]]

# p sorted_hash
#=> {-7=>1, -6=>2, 3=>3, 5=>4, 9=>5}

results = original_ary.map{ | num | sorted_hash[ num ] }
puts results.join( " " ) #=> 2 3 5 4 3 1

◆QZaw55cn4c · 2019/05/22(水) 19:16:47.93

>>70-71
アンカーが多すぎると投稿できないのです、ただそれだけです

◆QZaw55cn4c · 2019/05/22(水) 19:17:22.29

>>73
＞おだてれば猿も木に登るタイプだとみた。
痛いところを突きますね…

50 · 2019/05/22(水) 19:26:33.00

>2 3 5 4 3 1

これが、
2 3 6 5 3 1

みたいに、4 が無くなる・飛ばされるランキングだと、もっとややこしい！w

**デフォルトの名無しさん** · 2019/05/23(木) 09:23:03.57

前スレの920 Ruby

def f(a)
b={}
a .dup.sort.each{|v|b[v]=b.size+1 if not b.key v}
a.map{|v|b[v]}
end

p f([-6,3,9,5,3,-7])
[2, 3, 5, 4, 3, 1]

**デフォルトの名無しさん** · 2019/05/23(木) 12:32:00.03

>>34
>>79

一休さんみたいなトンチの効いた回答で、それはそれで楽しめました。

改めて問題を書き直します。

各桁を足し合わせたら引数で与えられた数になる数の集合全体から小さい順に(可能なら=0対策)5個返す関数を作れ。

例:
sumnum 12
> [39,48,57,66,75] <- 3 + 9 = 12, 4 + 8 = 12, 5 + 7 = 12, 6 + 6 = 12, 7 + 5 = 12

**デフォルトの名無しさん** · 2019/05/23(木) 12:33:09.81

>>34は>>15の間違い

**デフォルトの名無しさん** · 2019/05/23(木) 13:50:07.86

苗字で漢字の｢口｣を｢くち｣ではなく｢ぐち｣と読むのは
井口、矢口、田口の3つだけ
これマメな

**デフォルトの名無しさん** · 2019/05/23(木) 15:16:07.91

>>92
川口
ハイ論破

**デフォルトの名無しさん** · 2019/05/23(木) 16:02:19.12

ただの荒らし、蒸し蒸し by 山口

**デフォルトの名無しさん** · 2019/05/23(木) 17:19:50.40

>>90 OCaml
https://ideone.com/kvm79F

**デフォルトの名無しさん** · 2019/05/23(木) 18:37:52.11

>>90
Haskell

import Data.Char要らんかった。
take 5も問題と違うけど外に追い出した方が応用効きそう。

main = (print.take 5.sumnum) 12

sumnum 0 = [0]
sumnum n |n < 0 = error "Please n >= 0 number"
sumnum n = [x | x <- [1..], n == sum [read [a]| a <- show x]]

>>95
OCamlで無限リスト処理どうすんだろと疑問だったので、後で精読させて頂きますm(_ _)m

◆QZaw55cn4c · 2019/05/23(木) 18:40:43.46

>>92
谷口
関口
合口・相口・藍口・青口・赤口・秋口・明口… https://name.sijisuru.com/Fname/search?option=1&;moji=%E5%8F%A3&pages=0&kanjilen=0&kanalen=0&romalen=0

**デフォルトの名無しさん** · 2019/05/23(木) 19:39:17.51

>>97 もう相手にすんな。お題にするなら、

その9つの名前の読み仮名のあいうえお順に並べよ。

谷口・関口・合口・相口・藍口・青口・赤口・秋口・明口

読み仮名を持ってくるのが難しそうだけどな。

**デフォルトの名無しさん** · 2019/05/23(木) 21:02:26.03

aを要素の型がIntである長さNの配列、k、cを型がIntである変数とする。
{P}a[a[k]]=c;{a[a[k]]!=c}
Hoare tripleが成立するためのなるべく弱いPを示せ

◆QZaw55cn4c · 2019/05/23(木) 21:06:01.11

>>99
教えてください
P は何ですか？
{ } とは何を表しているのですか？

＞{P}a[a[k]]=c;{a[a[k]]!=c}

**デフォルトの名無しさん** · 2019/05/23(木) 21:17:28.82

>>100
https://i.imgur.com/CRuu9do.jpg
https://i.imgur.com/DKfpAvB.jpg

**デフォルトの名無しさん** · 2019/05/23(木) 21:38:26.52

sumnum、引数に10000とか与えたら答え返ってこなさそう
引数に1億とかは文字列長が千万とかになるから無理でも仕方ないけど、1万位は対応したいね

**デフォルトの名無しさん** · 2019/05/23(木) 23:35:27.08

>>102
下位桁に9が並ぶだけじゃね？

**デフォルトの名無しさん** · 2019/05/23(木) 23:45:44.19

>>103 知らない言語ばかりでよく読めてないんだが、今までの提出って1から順に試してね？
それだと当然結果が返ってこないが
違ったらすまん

**デフォルトの名無しさん** · 2019/05/24(金) 00:19:46.43

QZは相変わらず頭が悪い癖にプライドだけは高いな

**デフォルトの名無しさん** · 2019/05/24(金) 00:38:02.83

>>92は「必ずレスがもらえるレス」として有名な文らしいな
案の定わんさかレスの付いてること

**デフォルトの名無しさん** · 2019/05/24(金) 01:07:12.76

>>99 何語？

**デフォルトの名無しさん** · 2019/05/24(金) 01:41:24.00

>>11 閑話休題凸包
https://i.imgur.com/rMEhakE.jpg

**デフォルトの名無しさん** · 2019/05/24(金) 02:55:43.78

>>108 この凸包図を眺めてると、正解の正方形は左辺の一番長い線を1辺とした正方形になりそうだが、それをどうやって求めるのか。

How to find the minimum-area-rectangle (MAR) fitted on the given points?
https://gis.stackexchange.com/questions/22895/finding-minimum-area-rectangle-for-given-points

最初に書いた人は、凸包を求めて重心を中心として1度ずつ回転させるやり方を考えたらしいが、下の方で良い解法のコメントが付いてた。

https://i.stack.imgur.com/ExZl3.png

少しずつ回転させるのではなくて、長方形の1辺は必ず凸包の辺のどれかと重なってるはずだから、凸包の辺の角度だけをとって試せば良いとのこと。
これなら重心を求める必要もないし、時間はかからない。

長方形が求まったら、座標系の中に入る正方形にすれば良いがはみ出してたら、参考解かな。

このアルゴリズムは、
The algorithm you are looking for is known in polygon generalisation as "smallest surrounding rectangle".
凸包最小長方形の解法とでも言えば良いのかな。

**デフォルトの名無しさん** · 2019/05/24(金) 06:39:15.19

>>109
正方形を求める場合で凸包がひし形の場合、その方法はうまくいかないきがす？

**デフォルトの名無しさん** · 2019/05/24(金) 09:32:40.58

今回のアルゴリズムは、最小の正方形を求める方法だけじゃなくて、グラフの境界との交差判定もあるから
最小の求め方だけではなく、2番め以降についても正しく判定できないといけない上に、回答が一つに定まらない可能性もあるんだよね

**デフォルトの名無しさん** · 2019/05/24(金) 09:46:10.43

与えられた点を全て含む凸包全体からなる集合の濃度は明らかに連続体濃度なんだから2番目なんて存在しないぞ

**デフォルトの名無しさん** · 2019/05/24(金) 10:02:31.57

あ、凸包じゃなくて凸多角形な

**デフォルトの名無しさん** · 2019/05/24(金) 10:35:59.86

>>112
書いててあれ？と思てったけど、たしかにそうだ。
俺では解けなさそうだ。

**デフォルトの名無しさん** · 2019/05/24(金) 11:52:18.57

>>111 1辺から正方形を作る場合は、その正方形が全ての凸包の頂点を全て含むような大きさでなければならない。
この場合6辺あるから、そのような６つの正方形を作ってその中の最小のものを求めることになる。

面倒なのはそれが座標系に入らないといけないから場合によっては辺に平行移動しないといけないかも知れない。
すると、>>112 の言うように正方形の位置は変わるかもしれないけど、辺の長さが合ってれば正解だろうね。
（この場合は座標系に入るだろうからとりあえずは平行移動は考えないでも良いかも）

**デフォルトの名無しさん** · 2019/05/24(金) 12:12:24.29

>>110 どんな凸包体でも求まるよ。　1辺の長さが凸包体の辺の長さと一致させるわけじゃないよ。

全ての頂点を含む直方体を作る。　この求め方も工夫が必要そう。
1辺を伸ばした直線上に全ての頂点から垂線を引いて、一番外の距離を直方体の1辺とするんだろうな。
同じように他辺も求める。

**デフォルトの名無しさん** · 2019/05/24(金) 12:51:12.25

>>116
雑な書き殴りですまん
https://i.imgur.com/v8rWTSf.png

さらにややこしいのは、凸包の頂点が正方形の辺上に位置して、
頂点に存在しないことのほうが多いのも難くする要因の一つ

**デフォルトの名無しさん** · 2019/05/24(金) 13:09:58.32

>>117 あ、そうか。

**デフォルトの名無しさん** · 2019/05/24(金) 18:00:01.45

>>11 色々見たけど、画像認識の境界を探す為にある程度人気のある話題みたいだが、完全を求めるのではなく、だいたいで良いからスピードの速いのが良いとしてるみたいだね。境界自体があやふやなものだし。

厳密にやるとしても、長方形と正方形ではかなり条件が違う。

全ての点が正方形に入るのなら、一つの候補は凸包の対角上の点が一番離れているところを正方形の対角とした正方形が一つの候補ではないだろうか。
直交正方形が最大だからそこまでを調べれば良いけど、それだけをしらみつぶしに調べてどれだけ時間がかかるかだな。
それをはみ出る点がある場合にどうゴニョゴニョするかだけど、条件が絞れればスピードは速くなる。

一般的にはポイント数は膨大な数だから、条件を絞り込む方法が重要になりそう。

しかし、こんな例題はどこにでもありそうで殆どサンプルがないのは時間がかかりすぎて簡単に試せないのかな、今回はポイント数が少ないからそれほどではないとは思うけど。

**デフォルトの名無しさん** · 2019/05/24(金) 18:05:08.54

>>119 文章が変な順になっててごめん。

全ての点が正方形に入るのなら、一つの候補は凸包の対角上の点が一番離れているところを正方形の対角とした正方形が一つの候補ではないだろうか。

それをはみ出る点がある場合にどうゴニョゴニョするかだけど、条件が絞れればスピードは速くなる。

直交正方形が最大だからそこまでを調べれば良いけど、それだけをしらみつぶしに調べてどれだけ時間がかかるかだな。

**デフォルトの名無しさん** · 2019/05/24(金) 18:27:30.58

計算両を優先するなら、座標軸を基準にとって大雑把に取るべきじゃないのかな
これなら、ゲームのコリジョン検出で使われる方法そのままだし

**デフォルトの名無しさん** · 2019/05/24(金) 18:52:18.42

点の数は関係なくね？
任意の3点を選んでその内部にある点は無いものとして考えても同じなんだから

**デフォルトの名無しさん** · 2019/05/24(金) 19:02:15.89

いや、関係あるか
頂点のめちゃくちゃ多い凸多角形になったら計算量明らかに増えるもんな

**デフォルトの名無しさん** · 2019/05/25(土) 18:51:08.08

>>11 なんかかなりの難問に思えてきたな。解法への足がかりが見えない。凸包までは比較的簡単にたどり着いたけどそれからが闇の中。
凸包の重心が何か使えるだろうか？

最小包含円という言葉もあるようだが、少なくとも正方形の辺はこの円の直径以下。

**デフォルトの名無しさん** · 2019/05/25(土) 19:01:54.73

>>124 取り敢えずこの問題を『凸包正方形』
とでも呼びますか。

**デフォルトの名無しさん** · 2019/05/25(土) 20:41:54.94

三角形に分解してみる?

**デフォルトの名無しさん** · 2019/05/25(土) 21:12:11.52

>>112
連続体濃度でかつ二番目に小さな値のある集合
{0, 1} ∪ (2, ∞)

**デフォルトの名無しさん** · 2019/05/25(土) 22:13:07.00

>>11
ポイントが(136,577), (110,927)の2つだけならどうなる?

**デフォルトの名無しさん** · 2019/05/25(土) 22:15:27.93

>>128
それ対角線の正方形しかないやろ

**デフォルトの名無しさん** · 2019/05/26(日) 01:40:13.82

以下はｵﾚなりに考えた仮説
1）2点で正方形の内側に接するのは何らかの平べったい形、対角にて頂点が接するので45°
2）3点で接するのは、細長い三角形あるいはそれに準じた形、角度の計算は…?不明
　または凸包の一辺が正方形の辺に接する形
3）4点で接するのは、細長い三角形あるいはそれに準じた形、角度の計算は…?不明
　または凸包の一辺が正方形の辺に接する形
4）5点以上で接する場合は、凸包の一辺が正方形の辺に接する

「対角にて頂点が接する形の角度は45°」
「凸包の一辺が正方形の辺に接する形は凸包の辺の角度」
これらは角度が分かるので回転変化･逆変換を使って
外側の最小の斜め正方形の候補を探索することは可能だが、
角度が良く分からない形の解法が、まだ見出せていない

**デフォルトの名無しさん** · 2019/05/26(日) 01:44:08.13

凸包の一辺が正方形の辺に接するおよび二点が対角に接する場合に限った解法
なら難しくないんだがな…

**デフォルトの名無しさん** · 2019/05/26(日) 01:59:58.39

>>129
それは正方形が(0,0)-(999,999)からはみでてまうな

**130** · 2019/05/26(日) 17:27:59.46

>>11 外側の正方形 Perl5、但し>>130>>131の「凸包の一辺が正方形の辺に接する」または「細い菱形のような形が
正方形の対角2点で接する」場合について求てみた。凸包を求める処理は略し、二点間の辺を総当りで計算している。
use List::Util qw{min max pairkeys pairvalues};
@s=qw{136 577 110 927 472 199 157 808 388 598 94 31 388 157 325 409 787 897 850 598};
@X = pairkeys @s; @Y = pairvalues @s;
sub sp {$_[0]*$_[2] + $_[1]*$_[3]}
sub rt {
　@e = (cos $th, -sin $th); @f = (sin $th, cos $th);
　my @x = map{sp @e, $X[$_], $Y[$_]} 0..$#X;
　my @y = map{sp @f, $X[$_], $Y[$_]} 0..$#Y;
　@x = (min(@x), max(@x)); @y = (min(@y), max(@y));
　$h = (max $x[1] - $x[0], $y[1] - $y[0]) / 2;
　$cx = ($x[1] + $x[0]) / 2; $cy = ($y[1] + $y[0]) / 2;
　@x = ($cx - $h, $cx + $h); @y = ($cy - $h, $cy + $h);
　($e[1], $f[0]) = (-$e[1], -$f[0]);
　@x = map{sp @e, $x[$_], $y[$_]} 0..1;
　@y = map{sp @f, $x[$_], $y[$_]} 0..1;
　@x = (min(@x), max(@x)); @y = (min(@y), max(@y));
　(\@x, \@y, 2*$h) }
for $i (0..@X-2) { for $j ($i+1..$#X) {
　($dx, $dy) = ($X[$j] - $X[$i], $Y[$j] - $Y[$i]);
　($dx, $dy) = (-$dx, -$dy) if $dx < 0;
　$l = sqrt($dx*$dx + $dy*$dy);
　$th = $dx > abs($dy) ? -atan2($dy, $dx) : atan2($dx, $dy);
　($X, $Y, $w) = &rt;
　push @t, +{i,$i,j,$j,dx,$dx,dy,$dy,l,$l,th,$th,X,$X,Y,$Y,w,$w};
　$th += 3.14159265358979/4; ($X, $Y, $w) = &rt;
　push @t, +{i,$i,j,$j,dx,$dx,dy,$dy,l,$l,th,$th,X,$X,Y,$Y,w,$w};
} }
@t = sort{$a->{w}<=>$b->{w}} grep{0<=$_->{X}[0]and$_->{X}[1]<=999 and 0<=$_->{Y}[0]and$_->{Y}[1]<=999} @t;
do {@x = @{$t[$_]->{X}}; @y = @{$t[$_]->{Y}};
　printf"%d: (%7.3f, %7.3f)-(%7.3f, %7.3f): w=%3.3f\n",$_+1,$x[0],$y[0],$x[1],$y[1],$t[$_]->{w}} for 0..5;

**デフォルトの名無しさん** · 2019/05/26(日) 17:29:47.07

>>133 の実行例

~ $ perl 14_11.pl
1: ( 48.607, 27.043)-(863.062, 983.177): w=891.576
2: ( 45.920, 20.484)-(869.713, 849.356): w=892.353
3: ( 32.627, 29.170)-(901.066, 949.457): w=895.142
4: ( 24.000, 31.000)-(920.000, 927.000): w=896.000
5: ( 24.000, 31.000)-(920.000, 927.000): w=896.000
6: ( 14.845, 32.823)-(931.567, 907.397): w=896.130

検算してないので、もしバグっていたらｺﾞﾒﾝﾁｬｲ、（ゝω・）ﾃﾍﾍﾟﾛ

**デフォルトの名無しさん** · 2019/05/26(日) 17:38:51.62

>>133 ｽﾏｿ、「正方形の4点の座標を示せ」と書かれていたので、出力処理を少し修正
use List::Util qw{min max pairkeys pairvalues};
@s=qw{136 577 110 927 472 199 157 808 388 598 94 31 388 157 325 409 787 897 850 598};
@X = pairkeys @s; @Y = pairvalues @s;
sub sp {$_[0]*$_[2] + $_[1]*$_[3]}
sub rt {
　@e = (cos $th, -sin $th); @f = (sin $th, cos $th);
　my @x = map{sp @e, $X[$_], $Y[$_]} 0..$#X;
　my @y = map{sp @f, $X[$_], $Y[$_]} 0..$#Y;
　@x = (min(@x), max(@x)); @y = (min(@y), max(@y));
　$h = (max $x[1] - $x[0], $y[1] - $y[0]) / 2;
　$cx = ($x[1] + $x[0]) / 2; $cy = ($y[1] + $y[0]) / 2;
　@x = ($cx - $h, $cx + $h); @y = ($cy - $h, $cy + $h);
　($e[1], $f[0]) = (-$e[1], -$f[0]);
　@x = map{sp @e, $x[$_], $y[$_]} 0..1;
　@y = map{sp @f, $x[$_], $y[$_]} 0..1;
　@x = (min(@x), max(@x)); @y = (min(@y), max(@y));
　(\@x, \@y, 2*$h) }
for $i (0..@X-2) { for $j ($i+1..$#X) {
　($dx, $dy) = ($X[$j] - $X[$i], $Y[$j] - $Y[$i]);
　($dx, $dy) = (-$dx, -$dy) if $dx < 0;
　$l = sqrt($dx*$dx + $dy*$dy);
　$th = $dx > abs($dy) ? -atan2($dy, $dx) : atan2($dx, $dy);
　($X, $Y, $w) = &rt;
　push @t, +{i,$i,j,$j,dx,$dx,dy,$dy,l,$l,th,$th,X,$X,Y,$Y,w,$w};
　$th += 3.14159265358979/4; ($X, $Y, $w) = &rt;
　push @t, +{i,$i,j,$j,dx,$dx,dy,$dy,l,$l,th,$th,X,$X,Y,$Y,w,$w};
} }
@t = sort{$a->{w}<=>$b->{w}} grep{0<=$_->{X}[0]and$_->{X}[1]<=999 and 0<=$_->{Y}[0]and$_->{Y}[1]<=999} @t;
do {@x = @{$t[$_]->{X}}; @y = @{$t[$_]->{Y}};
　printf"%d: (%6.3f, %6.3f), (%7.3f, %6.3f), (%6.3f, %7.3f), (%7.3f, %7.3f): w=%3.3f\n",
　　$_+1,$x[0],$y[0],$x[1],$y[0],$x[0],$y[1],$x[1],$y[1],$t[$_]->{w}} for 0..5;