結果

問題 No.1932 動く点 P / Moving Point P
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:43:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,236 ms / 6,000 ms
コード長 3,219 bytes
コンパイル時間 145 ms
コンパイル使用メモリ 82,584 KB
実行使用メモリ 171,700 KB
最終ジャッジ日時 2025-03-20 20:43:41
合計ジャッジ時間 20,427 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
import sys

class SegmentTreeNode:
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.left = None
        self.right = None
        self.a = 1.0
        self.b = 0.0
        self.tx = 0.0
        self.c = 0.0
        self.d = 1.0
        self.ty = 0.0

def build(l, r, data):
    node = SegmentTreeNode(l, r)
    if l == r:
        op = data[l - 1]
        node.a, node.b, node.tx, node.c, node.d, node.ty = op
    else:
        mid = (l + r) // 2
        node.left = build(l, mid, data)
        node.right = build(mid + 1, r, data)
        a1 = node.right.a
        b1 = node.right.b
        tx1 = node.right.tx
        c1 = node.right.c
        d1 = node.right.d
        ty1 = node.right.ty
        a2 = node.left.a
        b2 = node.left.b
        tx2 = node.left.tx
        c2 = node.left.c
        d2 = node.left.d
        ty2 = node.left.ty
        node.a = a1 * a2 + b1 * c2
        node.b = a1 * b2 + b1 * d2
        node.tx = a1 * tx2 + b1 * ty2 + tx1
        node.c = c1 * a2 + d1 * c2
        node.d = c1 * b2 + d1 * d2
        node.ty = c1 * tx2 + d1 * ty2 + ty1
    return node

def query(node, s, t, res):
    if node.r < s or node.l > t:
        return
    if s <= node.l and node.r <= t:
        res.append(node)
        return
    query(node.left, s, t, res)
    query(node.right, s, t, res)

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    data = []
    for _ in range(N):
        p = float(input[ptr])
        q = float(input[ptr+1])
        r = float(input[ptr+2])
        ptr +=3
        theta = math.radians(r)
        ct = math.cos(theta)
        st = math.sin(theta)
        a = ct
        b = -st
        tx = p * (1.0 - ct) + q * st
        c = st
        d = ct
        ty = q * (1.0 - ct) - p * st
        data.append( (a, b, tx, c, d, ty) )
    if N == 0:
        root = None
    else:
        root = build(1, N, data)
    Q = int(input[ptr])
    ptr +=1
    for _ in range(Q):
        s = int(input[ptr])
        t = int(input[ptr+1])
        x = float(input[ptr+2])
        y = float(input[ptr+3])
        ptr +=4
        nodes = []
        if root:
            query(root, s, t, nodes)
        current_a = 1.0
        current_b = 0.0
        current_tx = 0.0
        current_c = 0.0
        current_d = 1.0
        current_ty = 0.0
        for node in nodes:
            a = node.a
            b = node.b
            tx = node.tx
            c_node = node.c
            d_node = node.d
            ty = node.ty
            new_a = a * current_a + b * current_c
            new_b = a * current_b + b * current_d
            new_tx = a * current_tx + b * current_ty + tx
            new_c = c_node * current_a + d_node * current_c
            new_d = c_node * current_b + d_node * current_d
            new_ty = c_node * current_tx + d_node * current_ty + ty
            current_a, current_b, current_tx, current_c, current_d, current_ty = new_a, new_b, new_tx, new_c, new_d, new_ty
        x_new = current_a * x + current_b * y + current_tx
        y_new = current_c * x + current_d * y + current_ty
        print("{0:.6f} {1:.6f}".format(x_new, y_new))

if __name__ == "__main__":
    main()
0