[KOITP] 다각형의 넓이

출    처 : http://koitp.org/problem/SDS_PRO_9_1/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	2205	127 (6%)	108

문제

이차원 평면에 점 N개로 이루어진 단순 다각형이 주어진다. 이때 이 다각형이 평면에서 차지하는 면적을 구해보자. 다각형의 면적은 반드시 0보다 크다.

입력

첫째 줄에 다각형을 이루는 점의 갯수 (1 ≦ N ≦ 100,000)이 주어지고,

둘째 줄 부터 N개의 점의 정수 좌표(-10^9 ≦ x, y ≦ 10^9)가 입력으로 주어진다.

다각형의 좌표는 시계 방향 또는 반시계 방향 순서로 주어진다.

출력

주어진 단순 다각형이 이루는 넓이를 소수 둘째 자리에서 반올림 한 값을 출력한다.

힌트

입력 예시

3
1 1
1 2
2 1

출력 예시

0.5

< Comment >

 외적을 이용하여 문제를 풀도록 되어있습니다. 점들이 시계방향 혹은 반시계 방향으로 주어지기 때문에, 입력받은 순서대로 각각을 p1, p2, p3..... pn 이라고 할 때, p1과 p2, p2와 p3 이런식으로 순서대로 외적을 진행하여 모두 곱합니다. 처음에 double 형을 이용하여 계산했었는데, 연산하는 과정에서 오차가 생겼는지 1개 오답이 발생하였습니다. 저는 일단 발생하던 문제를 BigDecimal 을 이용하여 해결하였고, 이외에도 어차피 포인트 값이 정수형이기 때문에 연산의 결과도 정수형이고, 소수점은 0 혹은 0.5밖에 나올 수 없습니다. 소수인지 홀수인지만 판별하여, 뒤에 소수점을 붙여주는 방식으로 진행하셔도 됩니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigDecimal;
import java.util.StringTokenizer;

public class Shapes {
	
	public static class Point {
		
		long x = 0;
		long y = 0;
		
		public Point (long x, long y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static int N = 0;
	public static Point[] points = null;

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		points = new Point[N];
		
		StringTokenizer st = null;
		long x = 0;
		long y = 0;
		for (int i = 0 ; i < N ; i++) {		// 시계방향으로 주어지는 값들
			
			st = new StringTokenizer(br.readLine());
			x = Long.parseLong(st.nextToken());
			y = Long.parseLong(st.nextToken());
			points[i] = new Point(x, y);
		}
		
		long result = 0;
		for (int i = 0 ; i < N - 1 ; i++) {
			
			result += outerProduct(points[i], points[i + 1]);
		}
		result += outerProduct(points[N-1], points[0]);
		BigDecimal res = new BigDecimal(Math.abs(result)).divide(new BigDecimal("2"));
		
		bw.write(String.format("%.1f", res));
		bw.flush();
		bw.close();
	}
	
	public static long outerProduct (Point a, Point b) {
		// 원점을 기준으로 벡터를 볼 때 외적
		long ret = (a.x * b.y) - (a.y * b.x);
		return ret;
	}
}