[過去ﾛｸﾞ] プログラミングのお題スレ Part14 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
11(21): 2019/05/19(日)12:12 ID:tgogs/mB(1/4) AAS
お題
(0,0)(0,999)(999,0)(999,999)のx,y 座標系の中の問題
次の20個の数値を先頭から2個ずつ取ってのx,y の位置に 10個のポイントがあるとする。
[136, 577, 110, 927, 472, 199, 157, 808, 388, 598, 94, 31, 388, 157, 325, 409, 787, 897, 850, 598]
(136,577) (110,927) 〜(850,598) 10ポイント
問題1 外側の正方形
全てのポイントが正方形の内側にあり、正方形の面積が一番小さくなる正方形の4点の座標を示せ。 但し正方形の座標は(999,999)の範囲内とする。
正方形は斜めもあり得る。 正方形の辺は必ず2点以上ポイントに重なっている。
省4
22: ◆QZaw55cn4c 2019/05/19(日)14:47 ID:8BTe2vpb(4/9) AAS
お題と回答
>>5 : >>6 >>10
>>9 : >>15
>>11:
>>19:
43: ◆QZaw55cn4c 2019/05/20(月)00:00 ID:V0YkyU13(1) AAS
>>41
小ネタの合間にめんどくさいものがポツポツあるかと >>11 とか
48(1): 2019/05/20(月)09:16 ID:m4uUuPD/(1) AAS
>>11 問題1の斜めにしない直行正方形までは出た。
xの範囲= (94, 31) (850, 598) 差 756
yの範囲= (94, 31) (110, 927) 差 896
1辺= 896
直行正方形 (94, 31) (990, 31) (94, 927) (990, 927)
次はこれを傾けていくんだな。これがムズイ。
49: 2019/05/20(月)13:11 ID:YvmdLvGf(1) AAS
>>11 x,y座標は ０〜999までの整数 辺の長さは斜めになった時は整数とは限らない。
62(2): ◆QZaw55cn4c 2019/05/21(火)22:17 ID:vwCWORvF(3/3) AAS
お題と回答
>>5 : 6 10 32 36 44
>>9 : 15 34 35
>>11 : 48
>>19 :
>>50 2chｽﾚ:tech :
2chｽﾚ:tech : 59 61
72(1): 2019/05/22(水)01:29 ID:BQdyZ7fR(2/3) AAS
>>11 は、多角形の中のドットの内外判定問題と言うのが確立されてるみたいね。
色んな方法があるみたいだが、簡単なのは、
Crossing Number Algorithm
らしい、ググってみると結構コンパクトなコード。
他も見てみたが、問題は境界線上にある点は多角形外と判定する事。
だから、そのままのロジックに手を入れないとした場合、使う側としてどう解決したら良いんだろう。
直行正方形を1ドットずつ大きくしてから回転させる？
それとも、多角形の中の多角形問題の方が適してるのかな？
この問題は結構勉強になる。 問題のイメージを掴むために、図形表示までやり始めたよ。 表示するとより楽しくなる。
108(1): 2019/05/24(金)01:41 ID:/EuQv4hQ(2/3) AAS
>>11 閑話休題 凸包
画像ﾘﾝｸ[jpg]:i.imgur.com
119(1): 2019/05/24(金)18:00 ID:ZpEEE6+U(1/2) AAS
>>11 色々見たけど、画像認識の境界を探す為にある程度人気のある話題みたいだが、完全を求めるのではなく、だいたいで良いからスピードの速いのが良いとしてるみたいだね。 境界自体があやふやなものだし。
厳密にやるとしても、長方形と正方形ではかなり条件が違う。
全ての点が正方形に入るのなら、一つの候補は凸包の対角上の点が一番離れているところを正方形の対角とした正方形が一つの候補ではないだろうか。
直交正方形が最大だからそこまでを調べれば良いけど、それだけをしらみつぶしに調べてどれだけ時間がかかるかだな。
それをはみ出る点がある場合にどうゴニョゴニョするかだけど、条件が絞れればスピードは速くなる。
一般的にはポイント数は膨大な数だから、条件を絞り込む方法が重要になりそう。
しかし、こんな例題はどこにでもありそうで殆どサンプルがないのは時間がかかりすぎて簡単に試せないのかな、今回はポイント数が少ないからそれほどではないとは思うけど。
124(1): 2019/05/25(土)18:51 ID:CqCnLPQm(1/2) AAS
>>11 なんかかなりの難問に思えてきたな。 解法への足がかりが見えない。 凸包までは比較的簡単にたどり着いたけどそれからが闇の中。
凸包の重心が何か使えるだろうか？
最小包含円 という言葉もあるようだが、少なくとも 正方形の辺はこの円の直径以下。
128(1): 2019/05/25(土)22:13 ID:u9k+LAdR(1) AAS
>>11
ポイントが(136,577), (110,927)の2つだけならどうなる?
133(2): 130 2019/05/26(日)17:27 ID:XOxN6P/y(1/7) AAS
>>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;
省22
138(2): 2019/05/26(日)18:33 ID:XOxN6P/y(6/7) AAS
>>11 外側の正方形 Perl5 凸包の辺が正方形の辺に接するまたは対角二点で接する場合、>>135の露骨なﾊﾞｸﾞ一個修正
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));
省22
139(1): 2019/05/26(日)18:37 ID:XOxN6P/y(7/7) AAS
>>138 実行例
~ $ perl 14_11.pl
1: ( 32.627, 29.170), (927.382, 55.475), ( 6.310,923.152), (901.066,949.457): w=895.142, th= -1.685°
2: (920.000,927.000), ( 24.000,927.000), (920.000, 31.000), ( 24.000, 31.000): w=896.000, th=180.000°
3: ( 24.000, 31.000), (920.000, 31.000), ( 24.000,927.000), (920.000,927.000): w=896.000, th= 0.000°
4: ( 14.845, 32.823), (910.733, 11.994), ( 35.680,928.226), (931.567,907.397): w=896.130, th= 1.332°
5: ( 18.819, 32.332), (914.819, 16.335), ( 34.819,928.046), (930.819,912.049): w=896.143, th= 1.023°
ちゃんと検算してないので、もしまだバグがいたらｺﾞﾒﾝﾁｬｲ、（ゝω・） ﾃﾍﾍﾟﾛ
検算方法考えた方がいいのかも。ちなみにwは正方形の幅、thは回転各[deg]
>>11 の内側の正方形についてはまだ考えていない。
140(3): 2019/05/26(日)20:05 ID:MaF2nVvH(1/2) AAS
>>11 おもろいな、初級問題だと文法の練習としてそれなりに勉強になる。
こう言うのはそれを超えていろんなパッケージ／ライブラリを駆使することになるから一皮剥けて勉強になる。
解けるか解けないか判らないけど楽しんでる。
勿論こう言うのは、言語の問題ではなく、ロジックの問題だと解っているんだが、ヒントとなる数字を出せるのは言語の力にもよるからそれはそれなりに面白い。
図形は直感的に推論が正しいかどうか判るから面白い。
画像ﾘﾝｸ[jpg]:i.imgur.com
凸包の重心は使えなさそうだな。
>>139 なんとなく変に感じるんだが。
画像ﾘﾝｸ[jpg]:i.imgur.com
省2
142: ◆QZaw55cn4c 2019/05/26(日)20:24 ID:CpBTYp0n(1/2) AAS
>>11
まずは「斜めは考えない」 外部ﾘﾝｸ:ideone.com
>>48
解が一致しました
143: ◆QZaw55cn4c 2019/05/26(日)20:28 ID:CpBTYp0n(2/2) AAS
お題と回答
>>5 : 6 10 32 36 44
>>9 : 15 34 35 79
>>11 : 48 (78) 138-139
>>19 :
>>50 2chｽﾚ:tech : 4 85 89
2chｽﾚ:tech : 59 61
>>90 : 95 96
>>99 :
146(3): 2019/05/27(月)03:33 ID:ZlNUfz2v(1) AAS
>>11 1)のみ やってみた。
図 外部ﾘﾝｸ:codepen.io
※ 途中で完全にJavaScriptのお遊びになってしまった。
(計算は別プログラムで、そのログを図にした)
一辺 = 890.70993168302
四点
x: [ 0.8027676391, 82.9114960624, 969.828819782, 887.7200913596]
y: [916.8907759982, 29.9734522778, 112.082180701, 998.9995044215]
157: 2019/05/28(火)01:02 ID:eILR4MCH(2/4) AAS
>>125 >>11 の問題1 に名前を与えるならさしずめ、最小包含正方形 かな。
312: ◆QZaw55cn4c 2019/06/09(日)13:42 ID:VJkUGCEU(1) AAS
お題と回答
>>5 : 6 10 32 36 44
>>9 : 15 34 35 79
>>11 : 48 (78) 138-139 (140) 142 146 151 154
>>19 :
>>50 2chｽﾚ:tech : 4 85 89
2chｽﾚ:tech == >>164 : 59 61 167 169 189 192 201 202
>>90 : 95 96
>>99 :
>>200 : 214 219
省3
624: 2019/06/26(水)01:05 ID:fhfivptN(1) AAS
>>575 >>623 それって、>>11 の入口問題だな。 俺も>>11 関連で知ったが、最小包含円って言葉は、このスレで何度か出てきてるぞ、
具体的な宇宙人の足跡データが、>>11 として最小包含円を求めよとした方がより具体的だな。 いくつか答えが出てるけど。
具体的なデーターを示さないと答えがバラバラになるぞ。 蟻人間の問題ってあやふやなのが多いな。
798: ◆QZaw55cn4c 2019/07/13(土)16:47 ID:KfP9prYE(1/4) AAS
>>9 : 15 34 35 79
>>11=>>575 : 48 (78) 138-139 (140) 142 146 151 154
>>19 :
>>50 2chｽﾚ:tech : 4 85 89
2chｽﾚ:tech == >>164 : 59 61 167 169 189 192 201 202
>>90 : 95 96
>>99 :
>>200 : 214 219
>>215 : 227
>>220 : 232 240 248 256 268
省3
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ ｱﾎﾞﾝOFF
ぬこの手 ぬこTOP 0.396s*