7463 Ellipse

문제 링크
5개의 점으로 표현된 타원의 넓이를 구하면 되는 간단한 문제다.

이차곡선 일반형을 이용해 By^2 + Cxy + Dx + Ey + F = -x^2으로 두고, 각 점을 대입해 연립방정식을 풀면 되는데, 가우스 소거법을 이용하였다. 다만 알고리즘의 한계로 행렬의 대각선 자리에 0이 들어가면 오류가 나기 때문에, 5개 식을 셔플해 주는 방식으로 문제를 해결하였다.
식을 완성하고 나면 알려진 공식에 따라 넓이를 구해 주면 된다. B^2-4C<0인 경우에만 타원이 되니 이를 체크해 주어야 하고, 오차 문제가 생각보다 커서 fractions 모듈을 이용하였다.

from fractions import Fraction
from random import shuffle
from math import pi
import sys
input = sys.stdin.readline


def gause():
    flag = True
    cnt = 0
    b = [[1]*6 for _ in range(5)]

    while flag:
        cnt += 1
        h = [0,1,2,3,4]
        shuffle(h)

        for i in range(5):
            w = h[i]
            for j in range(6):
                b[i][j] = a[w][j]

        flag = False
        for i in range(5):
            if b[i][i] == 0:
                flag = True
                break
            for j in range(i+1, 5):
                r = Fraction(b[j][i], b[i][i])
                for k in range(6):
                    b[j][k] -= r*b[i][k]
        
        if cnt > 120:
            return False

    x = [Fraction(1,1)]*5
    x[4] = Fraction(b[4][5], b[4][4])
    for i in range(3, -1, -1):
        x[i] = b[i][5]
        for j in range(i+1, 5):
            x[i] -= b[i][j]*x[j]
        x[i] /= b[i][i]

    d = 4*x[0]-x[1]**2
    if d <= 0: return False
    
    area = 2*(x[3]**2+x[0]*x[2]**2-x[1]*x[2]*x[3]-d*x[4])*(d**-1.5)
    area *= pi
    print(area)
    return True


def main():
    global a
    for _ in range(int(input())):
        a = [[1]*6 for _ in range(5)]

        point = list(map(int, input().split()))
        for i in range(5):
            x = point[i*2]
            y = point[i*2+1]
            
            a[i][0] = y**2
            a[i][1] = x*y
            a[i][2] = x
            a[i][3] = y
            a[i][5] = -x**2
        
        if not gause(): print('IMPOSSIBLE')


if __name__ == "__main__":
    main()

단순해 보이는 것과는 달리 생각보다는 오래 걸린거같다... 여담으로 5x5 역행렬을 구하는 방법도 생각해봤다가 넘겼는데, 가우스 소거법이 생각보다 고려해야 될 게 많아서 더 괜찮을 수도 있을 것 같다.