[백준][Java] 2166 다각형의 면적 - 골드5

문제 보기

https://www.acmicpc.net/problem/2166

 

 

풀이

골드5 문제치곤 쉬웠던 것 같다.

전에 수학 공부를 하며 익힌 얕은 지식을 이용해서 문제를 풀었다.

다각형은 삼각형들로 이루어져 있다는 것이다.

 

1. 신발끈 공식

 

보기에서 꼭짓점은 다각형을 이루는 순서대로 주어진다 했기 때문에

0, i-1, i번 인덱스를 꼭짓점으로 한 삼각형들을 구해서

전부 더해주는 방법을 사용하였다.

 

삼각형의 넓이를 구하는 방법 까진 떠올리지 않아서

구글 검색창을 이용했다.

 

https://hy-jiai.com/entry/%EC%84%B8-%EC%A0%90%EC%9D%98-%EC%A2%8C%ED%91%9C%EB%A1%9C-%EC%82%BC%EA%B0%81%ED%98%95%EC%9D%98-%EB%84%93%EC%9D%B4-%EA%B5%AC%ED%95%98%EB%8A%94-%EA%B3%B5%EC%8B%9D-%EC%82%AC%EC%84%A0%EA%B3%B5%EC%8B%9D-%EC%8B%A0%EB%B0%9C%EB%81%88%EA%B3%B5%EC%8B%9D

세 점의 좌표로 삼각형의 넓이 구하는 공식 (사선공식, 신발끈공식)

 

내가 참고한 건 위 블로그이다.

나도 수학에 대해 박식한 건 아니기 때문에 따로 신발끈 공식에 대해 찾아보면 좋을 것 같다.

아주 간편하게 세 점 만으로 삼각형의 넓이를 구할 수 있다.

 

for(int i = 0; i < N; i++) {
  String[] line = br.readLine().split(" ");
  vertices[i][0] = Integer.parseInt(line[0]);
  vertices[i][1] = Integer.parseInt(line[1]);

  if(i > 1) {
    area += (vertices[0][0] * vertices[i-1][1] +
        vertices[i-1][0] * vertices[i][1] +
        vertices[i][0] * vertices[0][1] -
        vertices[i-1][0] * vertices[0][1] -
        vertices[i][0] * vertices[i-1][1] -
        vertices[0][0] * vertices[i][1]) / 2.0;
  }
}

난 귀찮아서 공식에 계산을 때려 박았는데...

반복문을 잘 활용해 보는 것을 강추한다.

내가 짠 코드지만 솔직히 보기 좋아 보이진 않는다.

 

여기서 주의할 점은

위 그림 같이 볼록한 다각형 뿐만 아니라 오목한 다각형도 들어올 수 있기 때문에,

절댓값 처리는 넓이 계산을 마치고 하라는 것이다!

 

2. 자료형과 형식

 

그러나 당황스럽게도 매우 많이 틀렸다.

이유는 아래와 같다.

1. 최대 넓이는 40,000,000,000으로(절대값 100,000의 정수이기 때문에 200,000^2) int로 받을 경우 계산 중 overflow가 일어날 수 있음을 명심하자.
2. double으로 출력할 경우 범위를 초과해 지수표현(e가 들어가는 그것)으로 출력된다!

2번 때문에 최대 넓이를 테스트 해보기 전까지 답은 오리무중이었다.

 

DecimalFormat df = new DecimalFormat("#.0");
bw.write(df.format(Math.abs(area)));

 

Double의 포맷을 지정할 수 있는 DecimalFormat을 사용해 이 사태를 해결할 수 있었다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.text.DecimalFormat;

public class Main {
  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
    double[][] vertices = new double[N][2];
    double area = 0.0;
    for(int i = 0; i < N; i++) {
      String[] line = br.readLine().split(" ");
      vertices[i][0] = Integer.parseInt(line[0]);
      vertices[i][1] = Integer.parseInt(line[1]);

      if(i > 1) {
        area += (vertices[0][0] * vertices[i-1][1] +
            vertices[i-1][0] * vertices[i][1] +
            vertices[i][0] * vertices[0][1] -
            vertices[i-1][0] * vertices[0][1] -
            vertices[i][0] * vertices[i-1][1] -
            vertices[0][0] * vertices[i][1]) / 2.0;
      }
    }
    DecimalFormat df = new DecimalFormat("#.0");
    bw.write(df.format(Math.abs(area)));

    bw.flush();
    bw.close();

  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Gold/2166.%E2%80%85%EB%8B%A4%EA%B0%81%ED%98%95%EC%9D%98%E2%80%85%EB%A9%B4%EC%A0%81

CodingTest_AutoSave/백준/Gold/2166. 다각형의 면적 at main · MetroDefro/CodingTest_AutoSave