質問する

https://www.acmicpc.net/problem/15685
ドラッグカーブは、2 D座標平面で定義された3つのアトリビュートで構成されます.座標平面のx軸は→方向、y軸は↓方向です.

始点

開始方向

世代
0代目龍曲線は、下図のように長さ1の線分です.下図は(0,0)から始まり、開始方向は右側の0代目龍曲線です.

第1世代龍曲線は、第0世代龍曲線を終点として時計回りに90度回転し、第0世代龍曲線の終点に貼り付けられます.終点とは、始点から線分に沿って移動したときに最も遠い点です.

第2世代竜巻も第1世代を作る方法で作ることができます.(青い線分は新しく追加した線分を表します)

3代目龍曲線も2代目龍曲線で作ることができます.下図は3代目ドラゴンカーブです.

すなわち、K(K>1)世代龍曲線は、K-1世代龍曲線を端点を基準に時計回りに90度回転させ、端点に貼り付ける.
サイズは100×100人の人格にはN本の龍曲線がある.サイズ1×正方形の4つの頂点が曲線の一部をドラッグする正方形の個数であることを求めるプログラムを作成します.メッシュの座標は(x,y)と表され、0≦x≦100、0≦y≦100万の有効座標である.

入力

第1行はドラゴン曲線の個数N(1≦N≦20)を与える.2行目からN行は龍曲線の情報を与える.竜曲線の情報は4つの整数x,y,d,gからなる.xとyは龍曲線の起点,dは開始方向,gは世代である.(0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)
入力したドラゴンカーブはメッシュから外れません.ドラゴンカーブは互いに重なり合うことができます.
方向は0、1、2、3のいずれかで、次のことを意味します.
0:x座標が増加する方向(→)
1:y座標が減少する方向(↑)
2:x座標減少の方向(←)
3:y座標が増加する方向(↓)

しゅつりょく

最初の行のサイズは1です.×正方形を出力する4つの頂点は、竜曲線の一部の個数です.

アイデア

回転する点を時計回りに90度回転させる関数を作成します.世代ごとに、各ポイントをリストに回転します.4つの頂点が存在すると、数が1つ増えます.
✔find関数

i, j는 회전할 꼭짓점의 좌표이고 x, y는 기준점이다.
회전할 각 좌표에서 기준점의 좌표를 뺀다. 
뺀 좌표에서 x, y를 변경한 후, 90도 회전이므로 x좌표의 부호를 바꾼다.
바꾼 좌표를 기준점에 더해주면 i, j의 x, y에 대한 90도 회전한 점을 알 수 있다.

✔move関数

find를 이용해서 회전후 위치를 받아온다.
받아온 위치를 저장시키고 제일 처음 시작한 점이 제일 마지막 점이기 때문에 reverse를 해준다.
기존의 arr에 tmp를 더해서 return 한다.

✔️

q 리스트를 만들어두고 모든 꼭짓점을 저장한다.
처음 0세대인 경우 시작점과 끝 점을 가지고 원하는 세대만큼 반복한다.
반복이 끝나면 q리스트에는 사용된 꼭짓점만 존재하게 된다.
꼭짓점을 회전하면서 사각형을 만들 수 있는 모든 꼭짓점이 존재하면 ans+=1을 한다.

マイコードpython

n = int(input())
arr = [list(map(int, input().split())) for x in range(n)]

direction = [[1, 0], [0, -1], [-1, 0], [0, 1]]  #0, 1, 2, 3 각 시작 방향


def find(i, j, x, y):   #90도 회전했을 때 위치
    nx = -(j - y) + x
    ny = i - x + y
    return nx, ny


def move(arr):  #마지막 점 기준으로 모두 회전시키기
    tmp = []
    for i in range(len(arr)-1):
        nx, ny = find(arr[i][0], arr[i][1], arr[-1][0], arr[-1][1])
        tmp.append([nx, ny])
    tmp.reverse()
    return arr + tmp


q = []
for i in range(len(arr)):
    x = arr[i][0] + direction[arr[i][2]][0]
    y = arr[i][1] + direction[arr[i][2]][1]
    tmp = [[arr[i][0], arr[i][1]], [x, y]]
    #세대만큼 반복하기
    for j in range(arr[i][3]):
        tmp = move(tmp)
    #중복 제거하기 위함
    for k in tmp:
        if [k[0], k[1]] not in q:
            q.append(k)
ans = 0
d = [[-1, 0], [-1, 1], [0, 1]]
#꼭지점 모두 있는 사각형 찾기
for i in range(len(q)):
    x = q[i][0]
    y = q[i][1]
    chk = True
    for k in range(3):
        if [x+d[k][0], y+d[k][1]] not in q:
            chk = False
            break
    if chk:
        ans += 1
print(ans)