[BOJ][C#] 1198 삼각형으로 자르기

📕 문제

📌 링크

📗 접근 방식

• 점의 리스트를 받아서 모든 삼각형의 넓이를 구하고, 그 중에서 가장 큰 값을 찾아 결과로 출력합니다.
• 삼중 반복문을 이용하여 넓이를 구하고 최대값을 업데이트해준다.
  • 삼각형의 넓이는 헤론의 공식을 이용하여 계산 [해론의 공식 참고]

해론의 공식

해론의 공식은 세 변을 이용하여 삼각형의 넓이를 구하는 것으로
각 변을 $A$, $B$, $C$ 라고 할 때,
$s = {{A + B + C}\over 2}$ 이고
넓이 $S = \sqrt {s * (s - A) * (s - B) * (s - C)}$ 이다.

📘 코드

using System.Text;

namespace BOJ_1198
{
    class Program
    {
        static void Main()
        {
            using StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
            using StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

            List<(int, int)> list = new List<(int, int)>();
            int n = int.Parse(sr.ReadLine());
            for (int i = 0; i < n; i++)
            {
                int[] inputs = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);

                list.Add((inputs[0], inputs[1]));
            }

            double answer = 0;
            for (int a = 0; a < n; a++)
            {
                for (int b = a + 1; b < n; b++)
                {
                    for (int c = b + 1; c < n; c++)
                    {
                        // a와 b의 거리
                        double ab = Math.Sqrt(Math.Pow((list[a].Item1 - list[b].Item1), 2) + Math.Pow((list[a].Item2 - list[b].Item2),2));
                        // b와 c의 거리
                        double ba = Math.Sqrt(Math.Pow((list[b].Item1 - list[c].Item1), 2) + Math.Pow((list[b].Item2 - list[c].Item2),2));
                        // c와 a의 거리
                        double ca = Math.Sqrt(Math.Pow((list[c].Item1 - list[a].Item1), 2) + Math.Pow((list[c].Item2 - list[a].Item2),2));

                        double s = (ab + ba + ca) * 0.5;
                        double temp = Math.Sqrt(s * (s - ab) * (s - ba) * (s - ca));

                        answer = Math.Max(answer, temp);
                    }
                }
            }

            sw.Write(answer);
        }
    }
}

📙 오답노트

📒 알고리즘 분류

• 수학
• 브루트포스 알고리즘
• 기하학