문제
2차원 평면 위에 N개의 꼭짓점으로 이루어진 다각형이 주어질 때, 그 면적을 구하라.
입력
첫째 줄에 꼭짓점 수 N (3 ≤ N ≤ 10,000), 이후 N줄에 각 꼭짓점의 좌표 (x, y)가 순서대로 주어진다. 좌표 절댓값은 100,000 이하.
출력
다각형의 면적을 소수 첫째 자리까지 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 0 0 0 10 10 10 10 0 | 100.0 |
풀이
신발끈 공식(Shoelace Formula)을 사용하여 다각형의 면적을 계산한다.
- N개의 좌표를 배열에 저장하고, 마지막 인덱스에 첫 번째 좌표를 복사한다 (순환 연결)
sum_a = x[0]*y[1] + x[1]*y[2] + ... + x[N-1]*y[0]계산sum_b = x[1]*y[0] + x[2]*y[1] + ... + x[0]*y[N-1]계산- 면적 = |sum_a - sum_b| / 2.0
핵심 아이디어: 신발끈 공식은 꼭짓점 좌표만으로 다각형 면적을 O(N)에 계산한다. 좌표 값이 최대 10만이므로 곱셈 시 int 오버플로 방지를 위해 long 타입을 사용한다.
코드
package day349;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Day335BOJ2166다각형의면적 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
long[] x = new long[N + 1];
long[] y = new long[N + 1];
long sum_a = 0, sum_b = 0;
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
x[i] = Integer.parseInt(st.nextToken());
y[i] = Integer.parseInt(st.nextToken());
}
x[N] = x[0];
y[N] = y[0];
for (int i = 0; i < N; i++) {
sum_a += x[i] * y[i + 1];
sum_b += x[i + 1] * y[i];
}
String area = String.format("%.1f", (Math.abs(sum_a - sum_b) / 2.0));
bw.write(area);
br.close();
bw.flush();
bw.close();
}
}복잡도
- 시간: O(N)
- 공간: O(N)