-
[백준 - 2166번] 다각형의 면적 - Java //Wello Horld//Algorithm/BOJ(Baekjoon Online Judge) 2019. 7. 25. 15:19
이번에는 BOJ의 2166번 문제 "다각형의 면적"을 풀어보도록 하자
입력으로 첫째줄에 다각형의 꼭지점의 개수인 N 이 주어지고, 그다음 N개의 줄에 N개의 점의 x, y 좌표가 주어진다. 출력으로, 다각형의 면적을 구하면 되는 문제이다. 문제 자체는 간단하고, 수학만 할줄 알면 풀 수 있는 문제이다.
이번 문제에서 사용한 삼각형 넓이 공식은
- S = 1/2|(x1y2+x2y3+x3y1) - (x1y3+x2y1+x3y1)|
을 이용해서, 기준점을 두고 넓이를 구하는 방식을 선택했다. 그리고 입력으로 주어지는 x, y의 좌표가 다각형을 이루는 순서대로 되어있기 때문에, 입력된 순서대로 배열에 저장시킨 다음에, 처음을 고정시키고 그 다음 점부터 차례대로 3점을 뽑아서 넓이를 구해가는 방식으로 문제를 풀었다.
성공한 코드는 아래와 같다.
import java.io.*; import java.util.*; public class sample { 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()); Spot[] spot = new Spot[N + 1]; for (int i = 1; i <= N; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); long x = Long.parseLong(st.nextToken()); long y = Long.parseLong(st.nextToken()); spot[i] = new Spot(x, y); } long ans = 0; for (int i = 2; i < N; i++) { ans += area(spot[1], spot[i], spot[i + 1]); } ans = Math.abs(ans); if (ans % 2 == 1) System.out.println((ans / 2) + ".5"); else System.out.println((ans / 2) + ".0"); bw.flush(); br.close(); bw.close(); } public static long area(Spot first, Spot second, Spot third) { return ((first.x * second.y + second.x * third.y + third.x * first.y) - (first.x * third.y + second.x * first.y + third.x * second.y)); } } class Spot { long x, y; public Spot(long x, long y) { this.x = x; this.y = y; } }
문제 : https://www.acmicpc.net/problem/2166
'Algorithm > BOJ(Baekjoon Online Judge)' 카테고리의 다른 글
[백준 - 2261번] 가장 가까운 두 점 - Java //Wello Horld// (0) 2019.07.25 [백준 - 15904번] UCPC는 무엇의 약자일까? - Java //Wello Horld// (0) 2019.07.25 [백준 - 1915번] 가장 큰 정사각형 - Java //Wello Horld// (0) 2019.07.25 [백준 - 1016번] 제곱 ㄴㄴ수 - Java //Wello Horld// (0) 2019.07.23 [백준 - 1717번] 집합의 표현 - Java //Wello Horld// (0) 2019.07.23