roiti46's blog

主に競プロ問題の解説を載せてます

TopCoder SRM 652 Div2 Hard: NoRightTurnDiv2

Div1はUnratedとなってしまったSRM652。本番はEasyMed通したがMedの解答に苦戦してしまい、 1088 → 1080(-8)。

問題はこちら

問題

xy座標面上のN個の点が与えられる。任意の点からスタートして右側に曲がらず、かつ通った線をまたぐことなくすべての点を訪れることが可能か、可能なら条件に合う道順の1つを答えよ。

解答

外側からぐるぐる反時計まわりに点を訪れていくと、条件に合う道順を得ることができることが直感的にわかる。

まずy座標がもっとも小さく、さらにxがもっとも小さい点(x1,y1)を探す。 この点と(x0,y0) = (x1-0.5,y1)をスタートの点として次の点を探していく。(x0,y0は前の点、x1,y1は今の点だと考える) 次に進む点はまだ訪れていない点iのうち、2つのベクトル a = (x0-x1,y0-y1)とb = (x[i]-x1,y[i]-y1)のなす角度がもっとも大きい点となる。これをすべての点を訪れるまで繰り返していけばいい。図を描いてみてみるとわかるのだが、一番左下の点からスタートしているので、この方法で得られる次の点は訪れていない点のうちもっとも曲りの浅いもの道順を描く点となる。

こうしていけば外側の点から内側へぐるぐると点を訪れることができ、条件に合う道順を得ることができる。(問題ではそのような道順がないときは空のタプルを返せとなっていたが、そのような道順は必ず存在する)

def findPath(self, x, y):
    def calccos(x0,y0,x1,y1,x2,y2):
        ax,ay = x0-x1,y0-y1
        bx,by = x2-x1,y2-y1
        return (ax*bx+ay*by)/((ax**2+ay**2)**0.5*(bx**2+by**2)**0.5)
    
    N = len(x)
    x1,y1,si = x[0],y[0],0
    for i in xrange(N):
        if y[i] < y1 or y[i] == y1 and x[i] < x1:
            x1,y1,si = x[i],y[i],i
    
    x0,y0 = x1-0.5,y1
    used = [0]*N
    used[si] = 1
    ans = [si]
    
    for loop in xrange(N-1):
        cos = 1
        nxt = -1
        for i in xrange(N):
            if used[i]: continue
            tmp = calccos(x0,y0,x1,y1,x[i],y[i])
            if tmp < cos:
                cos = tmp
                nxt = i
        x0,y0,x1,y1 = x1,y1,x[nxt],y[nxt]
        ans.append(nxt)
        used[nxt] = 1
    
    return tuple(ans)