凸頂点の数
幾何はきついのですよ>_<
まあ、平面図形は空間図形よりはましですが。
前提
- まず、枠ごとに辺を割り振る(mapping)。このとき、反時計回りに繋がるように注意する。
- 1aは
[[0,0],[1,0],[2,0],[3,0],[2,19],[1,19],[0,0]].each_cons(2).to_aとなる。
最初の方針
- 重複している辺を取り除く。
- 残った辺について閉路を検出する。辺自体が反時計回りという情報を持っているので、辺の集合の前側(edges[i][0])だけ見れば良い。
- それぞれの閉路について、x,y座標を算出し、ベクトルに変換、隣接したベクトルの外積を計算する。外積が正なら180°未満の頂点である。
- 鈍角・鋭角ではなく凸か凹かなので内積ではなく外積。
- ドーナツ型の場合、内側の閉路が検出されることがある。しかし、 この閉路は時計回りになっている。 したがって、外積の符号は逆になる。外積が正の個数を数えればよいのは変わらないのである。
新しい方針
- しかし、これだけのものを60分でその場で実装できるはずはない。あくまで帰宅後の清書である。
- ロスタイム中に、 頂点数が1個ならば採用すべき頂点である ことがわかった。言い換えれば、伸びている辺が2本、である。
- ただし、00が含まれる場合は一番内側の頂点を除けば良い。
コード
清書含みます。変数名も多少まともに。
tyama_henae03.rb
#!/usr/bin/ruby
#http://qiita.com/Nabetani/items/b8bf742d278c6cf501aa
#http://nabetani.sakura.ne.jp/hena/orde03nofconv/
D=[0,1,1,0,0,1,1,0,0,1]
Vertex=D.each.with_index(1).map{|e,r|
20.times.map{|i|Complex(r*Math.cos(-(2*i+e)*Math::PI/20),r*Math.sin(-(2*i+e)*Math::PI/20))}
}
def mapping(s)
if s=='00'
(20.times.flat_map{|i|[[0,i],[1,i]]}+[[0,0]]).each_cons(2).map(&:reverse)
else
n,m=s[0].to_i-1,s[1].ord-97
f=n%2
[
[n*2,(m+n/2)%20],
[n*2+1,(m+n/2+f)%20],
[n*2+2,(m+n/2+f)%20],
[n*2+3,(m+n/2)%20],
[n*2+2,(m+n/2-(f^1))%20],
[n*2+1,(m+n/2-(f^1))%20],
[n*2,(m+n/2)%20]
].each_cons(2).to_a
end
end
STDOUT.sync=true
while gets
data=$_.chomp.scan(/../)
if false #どちらでも通ります
h=Hash.new(0)
edges=data.flat_map{|e|mapping(e)}
edges.map(&:sort).each{|e|e.each{|f|h[f]+=1}}
r=h.select{|k,v|v==2}.map(&:first)
if data.include?('00')
r.reject!{|x,y|x==0}
end
p r.size
else
h=Hash.new{|h,k|h[k]=[]}
data.flat_map{|e|mapping(e)}.each{|e|h[e.sort]<< e}
edges=h.select{|k,v|v.size==1}.flat_map(&:last)
r=0
while !edges.empty?
cycle=[edges.shift]
while cycle.last[1]!=cycle.first[0]
edges.size.times{|i|
if edges[i][0]==cycle.last[1]
cycle<<edges[i]
edges.delete_at(i)
break
end
}
end
cycle=cycle.map{|e|e.map{|n,m|Vertex[n][m]}}.map{|e,f|
f-e
}
r+=cycle.size.times.count{|i|
# 外積を手早く計算したくてComplexにした
(cycle[i].conj*cycle[(i+1)%cycle.size]).imag>0
}
end
p r
end
end
Author And Source
この問題について(凸頂点の数), 我々は、より多くの情報をここで見つけました https://qiita.com/cielavenir/items/a0d02ebec1d6cd218c13著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .