test/atcoder/abc/abc274_e_vec2d.test.py

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+09:00
• Problem: https://atcoder.jp/contests/abc274/tasks/abc274_e

Depends on

• cp_library/io/fast_io_cls.py
• cp_library/io/parser_cls.py
• cp_library/io/read_fn.py
• cp_library/io/write_fn.py
• cp_library/math/linalg/elm_wise_mixin.py
• cp_library/math/linalg/vec/vec2d_cls.py
• cp_library/math/linalg/vec/vec_cls.py

Code

# verification-helper: PROBLEM https://atcoder.jp/contests/abc274/tasks/abc274_e
# verification-helper: ERROR 1e-6
from math import inf

def main():
    N, M = read(tuple[int, ...])
    XY = read(list[Vec2D, N])
    PQ = read(list[Vec2D, M])
    pts = PQ+XY
    o = Vec2D(0,0)
    Tmask = (1 << M) -1
    Y = N+M
    Z = 1 << Y
    O = [o.distance(v) for v in pts]
    F = [1/(1 << mask.bit_count()) for mask in range(1 << M)]
    
    dp = [[inf]*Y for _ in range(Z)]
    for y in range(Y):
        mask = 1 << y
        dp[mask][y] = O[y]
        
    for mask in range(1,Z):
        factor = F[mask&Tmask]
        for y in range(Y):
            nmask = mask | 1 << y
            if mask == nmask: continue
            nc = dp[nmask][y]
            for l in range(Y):
                nc = min(nc, dp[mask][l] + pts[l].distance(pts[y]) * factor)
            dp[nmask][y] = nc
            
    full = Z-1
    ans = inf
    for tmask in range(1<<M):
        mask = full ^ tmask
        factor = F[mask&Tmask]
        for l in range(Y):
            nc = dp[mask][l] + O[l] * factor
            ans = min(ans, nc)
    write(f'{ans:0.10f}')

from cp_library.math.linalg.vec.vec2d_cls import Vec2D
from cp_library.io.read_fn import read
from cp_library.io.write_fn import write

if __name__ == "__main__":
    main()

# verification-helper: PROBLEM https://atcoder.jp/contests/abc274/tasks/abc274_e
# verification-helper: ERROR 1e-6
from math import inf

def main():
    N, M = read(tuple[int, ...])
    XY = read(list[Vec2D, N])
    PQ = read(list[Vec2D, M])
    pts = PQ+XY
    o = Vec2D(0,0)
    Tmask = (1 << M) -1
    Y = N+M
    Z = 1 << Y
    O = [o.distance(v) for v in pts]
    F = [1/(1 << mask.bit_count()) for mask in range(1 << M)]
    
    dp = [[inf]*Y for _ in range(Z)]
    for y in range(Y):
        mask = 1 << y
        dp[mask][y] = O[y]
        
    for mask in range(1,Z):
        factor = F[mask&Tmask]
        for y in range(Y):
            nmask = mask | 1 << y
            if mask == nmask: continue
            nc = dp[nmask][y]
            for l in range(Y):
                nc = min(nc, dp[mask][l] + pts[l].distance(pts[y]) * factor)
            dp[nmask][y] = nc
            
    full = Z-1
    ans = inf
    for tmask in range(1<<M):
        mask = full ^ tmask
        factor = F[mask&Tmask]
        for l in range(Y):
            nc = dp[mask][l] + O[l] * factor
            ans = min(ans, nc)
    write(f'{ans:0.10f}')

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''
from numbers import Number
from typing import Sequence
from math import gcd, sqrt

import typing
from collections import deque
from types import GenericAlias 
from typing import Callable, Collection, Iterator, Union
import os
import sys
from io import BytesIO, IOBase


class FastIO(IOBase):
    BUFSIZE = 8192
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        BUFSIZE = self.BUFSIZE
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        BUFSIZE = self.BUFSIZE
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    stdin: 'IOWrapper' = None
    stdout: 'IOWrapper' = None
    
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable

    def write(self, s):
        return self.buffer.write(s.encode("ascii"))
    
    def read(self):
        return self.buffer.read().decode("ascii")
    
    def readline(self):
        return self.buffer.readline().decode("ascii")

sys.stdin = IOWrapper.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper.stdout = IOWrapper(sys.stdout)
from typing import TypeVar
_T = TypeVar('T')

class TokenStream(Iterator):
    stream = IOWrapper.stdin

    def __init__(self):
        self.queue = deque()

    def __next__(self):
        if not self.queue: self.queue.extend(self._line())
        return self.queue.popleft()
    
    def wait(self):
        if not self.queue: self.queue.extend(self._line())
        while self.queue: yield
 
    def _line(self):
        return TokenStream.stream.readline().split()

    def line(self):
        if self.queue:
            A = list(self.queue)
            self.queue.clear()
            return A
        return self._line()
TokenStream.default = TokenStream()

class CharStream(TokenStream):
    def _line(self):
        return TokenStream.stream.readline().rstrip()
CharStream.default = CharStream()


ParseFn = Callable[[TokenStream],_T]
class Parser:
    def __init__(self, spec: Union[type[_T],_T]):
        self.parse = Parser.compile(spec)

    def __call__(self, ts: TokenStream) -> _T:
        return self.parse(ts)
    
    @staticmethod
    def compile_type(cls: type[_T], args = ()) -> _T:
        if issubclass(cls, Parsable):
            return cls.compile(*args)
        elif issubclass(cls, (Number, str)):
            def parse(ts: TokenStream): return cls(next(ts))              
            return parse
        elif issubclass(cls, tuple):
            return Parser.compile_tuple(cls, args)
        elif issubclass(cls, Collection):
            return Parser.compile_collection(cls, args)
        elif callable(cls):
            def parse(ts: TokenStream):
                return cls(next(ts))              
            return parse
        else:
            raise NotImplementedError()
    
    @staticmethod
    def compile(spec: Union[type[_T],_T]=int) -> ParseFn[_T]:
        if isinstance(spec, (type, GenericAlias)):
            cls = typing.get_origin(spec) or spec
            args = typing.get_args(spec) or tuple()
            return Parser.compile_type(cls, args)
        elif isinstance(offset := spec, Number): 
            cls = type(spec)  
            def parse(ts: TokenStream): return cls(next(ts)) + offset
            return parse
        elif isinstance(args := spec, tuple):      
            return Parser.compile_tuple(type(spec), args)
        elif isinstance(args := spec, Collection):  
            return Parser.compile_collection(type(spec), args)
        elif isinstance(fn := spec, Callable): 
            def parse(ts: TokenStream): return fn(next(ts))
            return parse
        else:
            raise NotImplementedError()

    @staticmethod
    def compile_line(cls: _T, spec=int) -> ParseFn[_T]:
        if spec is int:
            fn = Parser.compile(spec)
            def parse(ts: TokenStream): return cls([int(token) for token in ts.line()])
            return parse
        else:
            fn = Parser.compile(spec)
            def parse(ts: TokenStream): return cls([fn(ts) for _ in ts.wait()])
            return parse

    @staticmethod
    def compile_repeat(cls: _T, spec, N) -> ParseFn[_T]:
        fn = Parser.compile(spec)
        def parse(ts: TokenStream): return cls([fn(ts) for _ in range(N)])
        return parse

    @staticmethod
    def compile_children(cls: _T, specs) -> ParseFn[_T]:
        fns = tuple((Parser.compile(spec) for spec in specs))
        def parse(ts: TokenStream): return cls([fn(ts) for fn in fns])  
        return parse
            
    @staticmethod
    def compile_tuple(cls: type[_T], specs) -> ParseFn[_T]:
        if isinstance(specs, (tuple,list)) and len(specs) == 2 and specs[1] is ...:
            return Parser.compile_line(cls, specs[0])
        else:
            return Parser.compile_children(cls, specs)

    @staticmethod
    def compile_collection(cls, specs):
        if not specs or len(specs) == 1 or isinstance(specs, set):
            return Parser.compile_line(cls, *specs)
        elif (isinstance(specs, (tuple,list)) and len(specs) == 2 and isinstance(specs[1], int)):
            return Parser.compile_repeat(cls, specs[0], specs[1])
        else:
            raise NotImplementedError()

class Parsable:
    @classmethod
    def compile(cls):
        def parser(ts: TokenStream): return cls(next(ts))
        return parser


from typing import Iterable 
from math import hypot

import operator

class ElmWiseMixin:
    def elm_wise(self, other, op):
        if isinstance(other, Number):
            return type(self)(op(x, other) for x in self)
        if isinstance(other, Sequence):
            return type(self)(op(x, y) for x, y in zip(self, other))
        raise ValueError("Operand must be a number or a tuple of the same length")

    def __add__(self, other): return self.elm_wise(other, operator.add)
    def __radd__(self, other): return self.elm_wise(other, operator.add)
    def __sub__(self, other): return self.elm_wise(other, operator.sub)
    def __rsub__(self, other): return self.elm_wise(other, lambda x,y: operator.sub(y,x))
    def __mul__(self, other): return self.elm_wise(other, operator.mul)
    def __rmul__(self, other): return self.elm_wise(other, operator.mul)
    def __truediv__(self, other): return self.elm_wise(other, operator.truediv)
    def __rtruediv__(self, other): return self.elm_wise(other, lambda x,y: operator.truediv(y,x))
    def __floordiv__(self, other): return self.elm_wise(other, operator.floordiv)
    def __rfloordiv__(self, other): return self.elm_wise(other, lambda x,y: operator.floordiv(y,x))
    def __mod__(self, other): return self.elm_wise(other, operator.mod)

    def distance(self: 'ElmWiseMixin', other: 'ElmWiseMixin'):
        diff = other-self
        return hypot(*diff)
    
    def magnitude(vec: 'ElmWiseMixin'):
        return hypot(*vec)
    
    def norm(vec: 'ElmWiseMixin'):
        return vec / vec.magnitude()

class Vec(ElmWiseMixin, tuple, Parsable):
    def __new__(cls, *args):
        if len(args) == 1 and isinstance(args[0], Iterable):
            return super().__new__(cls, args[0])
        return super().__new__(cls, args)

    @classmethod
    def compile(cls, T: type = int, N = None):
        elm = Parser.compile(T)
        if N is None:
            def parse(ts: TokenStream):
                return cls(elm(ts) for _ in ts.wait())
        else:
            def parse(ts: TokenStream):
                return cls(elm(ts) for _ in range(N))
        return parse
  

class Vec2D(Vec):
    def __new__(cls, *args):
        if len(args) == 0:
            return super().__new__(cls, (0,0))
        return super().__new__(cls, *args)

    def elm_wise(self, other, op):
        if isinstance(other, Number):
            return Vec2D(op(self[0], other), op(self[1], other))
        if isinstance(other, Sequence):
            return Vec2D(op(self[0], other[0]), op(self[1], other[1]))
        raise ValueError("Operand must be a number or a tuple of the same length")

    def distance(v1: 'Vec', v2: 'Vec'):
        dx, dy = v2[0]-v1[0], v2[1]-v1[1]
        return sqrt(dx*dx+dy*dy)
    
    def distance2(v1: 'Vec', v2: 'Vec'):
        dx, dy = v2[0]-v1[0], v2[1]-v1[1]
        return dx*dx+dy*dy
    
    def magnitude(vec: 'Vec'):
        x, y = vec
        return sqrt(x*x+y*y)
    
    def magnitude2(vec: 'Vec'):
        x, y = vec
        return x*x+y*y
    
    def rot90(vec):
        x,y = vec
        return Vec2D(-y,x)
    
    def rot180(vec):
        x,y = vec
        return Vec2D(-x,-y)
    
    def rot270(vec):
        x,y = vec
        return Vec2D(y,-x)
    
    def flip_x(vec):
        x,y = vec
        return Vec2D(-x,y)
    
    def flip_y(vec):
        x,y = vec
        return Vec2D(x,-y)
    
    def cross(vec, other):
        return vec[0]*other[1] - vec[1]*other[0]
    
    def slope_norm(vec):
        x,y = vec
        if x == 0 and y == 0: return vec
        if x == 0: return Vec2D((0,1)) if y > 0 else Vec2D((0,-1))
        if y == 0: return Vec2D((1,0)) if x > 0 else Vec2D((-1,0))
        g = gcd(x,y)
        return Vec2D((x//g,y//g))
    
    @classmethod
    def compile(cls, T: type = int):
        elm = Parser.compile(T)
        def parse(ts: TokenStream):
            return cls(elm(ts), elm(ts))
        return parse


from typing import Iterable, Type, Union, overload

@overload
def read() -> Iterable[int]: ...
@overload
def read(spec: int) -> list[int]: ...
@overload
def read(spec: Union[Type[_T],_T], char=False) -> _T: ...
def read(spec: Union[Type[_T],_T] = None, char=False):
    if not char and spec is None: return map(int, TokenStream.default.line())
    parser: _T = Parser.compile(spec)
    return parser(CharStream.default if char else TokenStream.default)

def write(*args, **kwargs):
    '''Prints the values to a stream, or to stdout_fast by default.'''
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", IOWrapper.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()

if __name__ == "__main__":
    main()

Back to top page