#1177883 (PyPy3) No.3675 偏光板

• 問題: No.3675 偏光板
• ユーザー: 👑 みうね
• 提出日時: 2026-08-21 17:03:08
• 言語: PyPy3 (7.3.23)
• 結果: AC
• 実行時間: 1,743 ms / 2,000 ms
• コード長: 5,918 bytes
• コンパイル時間: 769 ms
• コンパイル使用メモリ: 95,956 KB
• 実行使用メモリ: 96,964 KB
• 最終ジャッジ日時: 2026-09-04 22:30:13
• 合計ジャッジ時間: 14,660 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 6
other	AC * 54

ソースコード

import sys
import math

def get_circle_area_in_rect(circles, X, Y):
    # 完全に他の円に覆われている円を除外する（計算量の削減）
    valid_circles = []
    for i in range(len(circles)):
        covered = False
        xi, yi, ri = circles[i]
        for j in range(len(circles)):
            if i == j: continue
            xj, yj, rj = circles[j]
            d2 = (xi - xj)**2 + (yi - yj)**2
            if d2 <= (rj - ri)**2 and ri <= rj:
                if ri < rj or i > j:
                    covered = True
                    break
        if not covered:
            valid_circles.append(circles[i])
            
    circles = valid_circles
    n = len(circles)
    total_area = 0.0
    
    # 1. 境界となる円弧の積分（グリーンの定理）
    for i in range(n):
        xi, yi, ri = circles[i]
        events = []
        base_cover = 0
        
        # 他の円との交点を計算し、被覆される角度区間をイベントとして記録
        for j in range(n):
            if i == j: continue
            xj, yj, rj = circles[j]
            dx = xi - xj
            dy = yi - yj
            d2 = dx*dx + dy*dy
            if d2 >= (ri + rj)**2 or d2 <= (ri - rj)**2:
                continue
                
            d = math.sqrt(d2)
            phi = math.atan2(yj - yi, xj - xi)
            
            # 余弦定理から交点の角度差分を求める
            val = (ri*ri + d2 - rj*rj) / (2 * ri * d)
            val = max(-1.0, min(1.0, val))
            dtheta = math.acos(val)
            
            start = phi - dtheta
            end = phi + dtheta
            
            # [-π, π] の範囲でラッピングを処理
            if start < -math.pi:
                events.append((start + 2*math.pi, 1))
                events.append((end, -1))
                base_cover += 1
            elif end > math.pi:
                events.append((start, 1))
                events.append((end - 2*math.pi, -1))
                base_cover += 1
            else:
                events.append((start, 1))
                events.append((end, -1))
                
        # 窓枠（長方形の4辺）との交点もイベント（カットポイント）として追加
        if abs(xi) <= ri:
            theta = math.acos(max(-1.0, min(1.0, -xi / float(ri))))
            events.extend([(theta, 0), (-theta, 0)])
        if abs(X - xi) <= ri:
            theta = math.acos(max(-1.0, min(1.0, (X - xi) / float(ri))))
            events.extend([(theta, 0), (-theta, 0)])
        if abs(yi) <= ri:
            theta = math.asin(max(-1.0, min(1.0, -yi / float(ri))))
            events.extend([(theta, 0), (math.pi - theta if theta >= 0 else -math.pi - theta, 0)])
        if abs(Y - yi) <= ri:
            theta = math.asin(max(-1.0, min(1.0, (Y - yi) / float(ri))))
            events.extend([(theta, 0), (math.pi - theta if theta >= 0 else -math.pi - theta, 0)])
                
        # 走査線の端点
        events.extend([(-math.pi, 0), (math.pi, 0)])
        events.sort(key=lambda x: x[0])
        
        cover = base_cover
        for k in range(len(events) - 1):
            angle, typ = events[k]
            cover += typ
            nxt_angle = events[k+1][0]
            
            # 他の円に覆われていない円弧の場合
            if cover == 0 and nxt_angle > angle + 1e-11:
                mid_angle = (angle + nxt_angle) / 2.0
                px = xi + ri * math.cos(mid_angle)
                py = yi + ri * math.sin(mid_angle)
                
                # 窓枠の「内側」にある円弧だけを採用
                if -1e-9 <= px <= X + 1e-9 and -1e-9 <= py <= Y + 1e-9:
                    dt = nxt_angle - angle
                    term1 = ri * ri * dt
                    term2 = xi * ri * (math.sin(nxt_angle) - math.sin(angle))
                    term3 = -yi * ri * (math.cos(nxt_angle) - math.cos(angle))
                    total_area += 0.5 * (term1 + term2 + term3)

    # 2. 窓枠上の境界積分の加算処理 (x=X と y=Y のみ Greenの定理の性質で残る)
    def merge_and_sum(intervals):
        if not intervals: return 0.0
        intervals.sort(key=lambda x: x[0])
        res = 0.0
        cur_start, cur_end = intervals[0]
        for s, e in intervals[1:]:
            if s <= cur_end:
                cur_end = max(cur_end, e)
            else:
                res += cur_end - cur_start
                cur_start = s
                cur_end = e
        res += cur_end - cur_start
        return res

    intervals_x = []
    for cx, cy, r in circles:
        if abs(X - cx) < r:
            dy = math.sqrt(r*r - (X - cx)**2)
            s, e = max(0.0, cy - dy), min(float(Y), cy + dy)
            if s < e: intervals_x.append((s, e))
    total_area += 0.5 * X * merge_and_sum(intervals_x)
    
    intervals_y = []
    for cx, cy, r in circles:
        if abs(Y - cy) < r:
            dx = math.sqrt(r*r - (Y - cy)**2)
            s, e = max(0.0, cx - dx), min(float(X), cx + dx)
            if s < e: intervals_y.append((s, e))
    total_area += 0.5 * Y * merge_and_sum(intervals_y)
    
    return total_area

def solve():
    input_data = sys.stdin.read().split()
    if not input_data: return
    
    X, Y, N = int(input_data[0]), int(input_data[1]), int(input_data[2])
    v_circles, h_circles = [], []
    
    idx = 3
    for _ in range(N):
        x, y, r = int(input_data[idx]), int(input_data[idx+1]), int(input_data[idx+2])
        d = input_data[idx+3]
        idx += 4
        if d == 'V':
            v_circles.append((x, y, r))
        else:
            h_circles.append((x, y, r))
            
    v_area = get_circle_area_in_rect(v_circles, X, Y)
    h_area = get_circle_area_in_rect(h_circles, X, Y)
    
    ans = X * Y - 0.5 * v_area - 0.5 * h_area
    print(f"{ans:.15f}")

if __name__ == '__main__':
    solve()