読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

Codeforces Round #339 (Div. 2) A, B, C 解答

結果

f:id:pakapa104:20160115174318p:plain

virtual participationですが初めて3完。 解けたものについて解答をまとめておきます。

A. Link/Cut Tree

codeforces.com

ki (i >= 0, iは整数) のうち、l以上r以下の数をすべて出力せよという問題。

コードを読めばたぶんわかる

l, r, k = map(long, raw_input().split())
x = 1L
while x < l:
    x *= k
if x > r:
    print -1
else:
    while x <= r:
        print x,
        x *= k

B. Gena's Code

codeforces.com

与えられたn個の数の積を出力する問題。

ただし単純にやるとオーバーフローするので、問題の性質を用いて文字列として対処する。

n個の数のうちn-1個はbeautiful number。beautiful numberとは、以下の条件を満たす数。

  • 10進数表記が'0'と'1'のみからなる かつ、
  • '1'は多くとも1個

具体的に書くと、0, 10, 100, 1000, ...

つまりbeautiful number は、答えにつく0の数にしか寄与しないことがわかる。よって解答の流れは以下の通りとなる。

  1. 0があればans = 0で終了(これは例外)
  2. beautiful numberなら0の数をカウント。not beautiful numberならansに記録しておく
  3. ans + カウントした数の'0'を出力
n = input()
ans = '1'
cnt = 0 #num of zero
a = map(str, raw_input().split())
for ax in a:
    if ax == '0':
        #zero
        print '0'
        break
    elif ax.count('1') == 1 and ax.count('0') == len(ax) - 1:
        #beautiful
        cnt += len(ax) - 1
    else:
        #not beautiful
        ans = str(ax)
else:
    print ans + '0' * cnt

C. Peter and Snow Blower

codeforces.com

Peterくんの持っている雪かき機は多角形です。ある点Pにひもでつなぐと、点Pの周りを円状に回って雪を掃除します。点Pと雪かき機の頂点の座標が与えられるので、雪を掃除できる面積を求めなさいという問題。

もう少し要約すると、求めるのは「多角形を点Pを中心として回転させたときにできる図形の面積」である。

たとえばsample caseでは以下のようにr_maxとr_minを定めると、答えは pi * (r_max ^2 - r_min ^2)で求まる。

f:id:pakapa104:20160115185026p:plain

上の図を見ると、「r_max = 点Pから最も遠い頂点までの距離, r_min = 点Pから最も近い頂点までの距離」で済むような気がする。しかし次の図のような場合には、r_minがこれを満たさない。r_max, r_minの正しい求め方は以下の通りである。

  • r_max = 点Pから最も遠い頂点までの距離
  • r_min = min(点Pから最も近い頂点までの距離, 点Pから各辺までの垂線の長さ)

f:id:pakapa104:20160115185927p:plain

点と直線との距離は例の公式で求める。垂線の足が辺の内部にあるかどうかを判断する必要があるので、垂線の足の座標はこのサイトの公式で求めた。

f:id:pakapa104:20160115190911p:plain

import math

n, px, py = map(int, raw_input().split())
rmin2, rmax2 = float("inf"), float("-inf")
li = []
for i in xrange(n):
    x, y = map(int, raw_input().split())
    li.append([x,y])
    r2 = (x - px)**2 + (y - py)**2
    rmin2 = min(rmin2, r2)
    rmax2 = max(rmax2, r2)

li.append(li[0])
for i in xrange(n):
    x1, y1 = li[i][0], li[i][1]
    x2, y2 = li[i+1][0], li[i+1][1]
    xd = x2 - x1
    yd = y2 - y1
    a = yd
    b = - xd
    c = xd * y1 - yd * x1
    numer = a*px + b*py + c
    denom = a**2 + b**2
    hx = px - 1.0 * a * numer / denom
    hy = py - 1.0 * b * numer / denom
    if min(x1, x2) <= hx <= max(x1, x2) and min(y1, y2) <= hy <= max(y1, y2):
        d2 = 1.0*abs(numer)**2 / denom 
        rmin2 = min(rmin2, d2)
print math.pi *(rmax2 - rmin2)