문제
2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다.
출력
첫째 줄에 면적을 출력한다. 면적을 출력할 때에는 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지 출력한다.
풀이
꼭짓점이 순서대로 주어질 때 다각형의 면적은 신발끈 공식으로 한 번에 계산할 수 있다. 각 변의 끝점을 이어 만든 외적 합을 더한 뒤 절반을 취하면 된다.
코드에서는 인접한 두 점에 대해 을 누적하고, 마지막 점과 첫 점도 한 번 더 연결한다. 절댓값을 취한 뒤 2로 나누면 최종 면적이 된다.
좌표를 직접 잘라 도형을 나눌 필요는 없다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
double[][] arr = new double[N][2];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
arr[i][0] = Double.parseDouble(st.nextToken());
arr[i][1] = Double.parseDouble(st.nextToken());
}
double sum = 0;
for (int i = 0; i < N; i++) {
sum += arr[i][0] * arr[(i + 1) % N][1];
sum -= arr[i][1] * arr[(i + 1) % N][0];
}
System.out.printf("%.1f", Math.abs(sum / 2));
}
}복잡도
- 시간 복잡도:
- 공간 복잡도:
마무리
다각형 면적 문제는 도형을 직접 분해하지 않아도 된다. 꼭짓점을 순서대로 한 바퀴 돌며 신발끈 공식을 적용하면 끝난다.
