글 읽기 - 스페셜 저지와 지문을 수정해 주세요.

ho94949 2년 전 2

원본 문제 같은 경우에, 절대 혹은 상대오차에 대한 얘기가 없이 소숫점 아래 3자리까지 출력하라고 되어 있고, 현재 문제의 예제는 정답과 비교했을 때 오차 범위 내에 들어오지 않습니다. 스페셜 저지를 절대오차 10^-3 이하를 허용하는 것으로 바꾸거나, 혹은 절대 및 상대 오차 10^-6 이하를 허용하는 것으로 바꾸고, 지문을 수정 해 주시기 바랍니다.

http://acm.student.cs.uwaterlo...

D.1.dat의 파일의 공백 형식이 잘 지켜지지 않았습니다. 또한, 실제 데이터를 확인해 본 결과 원의 좌표의 절댓값은 300이하, 반지름은 100이하 였으므로, 해당 사항을 문제에 명시해도 좋을 것 같습니다. 모든 원의 좌표와 반지름은 정수점이었지만, 사용하지는 않았습니다. 실제 N은 25이하, T는 23이하였습니다.

다음은 정답을 만드는 Python3 코드입니다. Decimal Module을 사용하므로 정확도가 매우 높습니다.

from decimal import *

getcontext().prec = 300


class Point:
    def __init__(self, re: Decimal, im: Decimal):
        self.re = re
        self.im = im

    def conj(self):
        return Point(self.re, -self.im)

    def norm(self):
        return self.re*self.re+self.im*self.im

    def abs(self):
        return self.norm().sqrt()

    def __iadd__(self, other):
        self.re += other.re
        self.im += other.im
        return self

    def __add__(self, other):
        return Point(self.re+other.re, self.im+other.im)

    def __isub__(self, other):
        self.re -= other.re
        self.im -= other.im
        return self

    def __sub__(self, other):
        return Point(self.re-other.re, self.im-other.im)

    def __mul__(self, other):
        if isinstance(other, Point):
            return Point(
                self.re*other.re-self.im*other.im,
                self.re*other.im+self.im*other.re)
        elif isinstance(other, Decimal):
            return Point(other*self.re, other*self.im)
        else:
            assert False

    def __truediv__(self, other):
        if isinstance(other, Decimal):
            return Point(self.re/other, self.im/other)
        else:
            assert False


def mCC(a: Point, b: Point, c: Point):
    b -= a
    c -= a
    d = 2*(b.conj()*c).im
    ans = (c*b.norm()-b*c.norm())*Point(Decimal(0), Decimal(-1)) / d

    return ans+a


def cos(x):
    """Return the cosine of x as measured in radians.

    The Taylor series approximation works best for a small value of x.
    For larger values, first compute x = x % (2 * pi).

    >>> print(cos(Decimal('0.5')))
    0.8775825618903727161162815826
    >>> print(cos(0.5))
    0.87758256189
    >>> print(cos(0.5+0j))
    (0.87758256189+0j)

    """
    getcontext().prec += 2
    i, lasts, s, fact, num, sign = 0, 0, 1, 1, 1, 1
    while s != lasts:
        lasts = s
        i += 2
        fact *= i * (i-1)
        num *= x * x
        sign *= -1
        s += num / fact * sign
    getcontext().prec -= 2
    return +s


def sin(x):
    """Return the sine of x as measured in radians.

    The Taylor series approximation works best for a small value of x.
    For larger values, first compute x = x % (2 * pi).

    >>> print(sin(Decimal('0.5')))
    0.4794255386042030002732879352
    >>> print(sin(0.5))
    0.479425538604
    >>> print(sin(0.5+0j))
    (0.479425538604+0j)

    """
    getcontext().prec += 2
    i, lasts, s, fact, num, sign = 1, 0, x, 1, x, 1
    while s != lasts:
        lasts = s
        i += 2
        fact *= i * (i-1)
        num *= x * x
        sign *= -1
        s += num / fact * sign
    getcontext().prec -= 2
    return +s


def pi():
    """Compute Pi to the current precision.

    >>> print pi()
    3.141592653589793238462643383

    """
    getcontext().prec += 2  # extra digits for intermediate steps
    three = Decimal(3)      # substitute "three=3.0" for regular floats
    lasts, t, s, n, na, d, da = 0, three, 3, 1, 0, 0, 24
    while s != lasts:
        lasts = s
        n, na = n+na, na+8
        d, da = d+da, da+32
        t = (t * n) / d
        s += t
    getcontext().prec -= 2
    return +s               # unary plus applies the new precision


def main():
    PI = pi()
    tc = 0
    while True:
        N = int(input())
        if N == 0:
            return

        ax, ay = map(Decimal, input().split())
        bx, by = map(Decimal, input().split())
        cx, cy = map(Decimal, input().split())

        o = mCC(Point(ax, ay), Point(bx, by), Point(cx, cy))

        minx = miny = o.re-ax
        maxx = maxy = o.im-ay

        for i in range(N):
            ang = 2*PI*i/N

            y = (o-Point(ax, ay))*Point(cos(ang), -sin(ang))

            minx = min(minx, y.re)
            miny = min(miny, y.im)
            maxx = max(maxx, y.re)
            maxy = max(maxy, y.im)

        ans = (maxx-minx)*(maxy-miny)

        tc += 1
        print(f'Polygon {tc}: {ans:.12f}')


if __name__ == '__main__':
    main()

sait2000 2년 전 0

분류가 질문으로 되어있어요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

스페셜 저지와 지문을 수정해 주세요.

ho94949 2년 전 2

sait2000 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말