728x90
2166 - 다각형의 면적
https://www.acmicpc.net/problem/2166

문제
2차원 평면상에 N(3 <= N <= 10,000)개의 점으로 이뤄진 다각형
=> 다각형의 면적
입력
첫째 줄: N
다음 N개의 줄: 다각형을 이루는 순서대로의 x, y좌표 (x, y < 100,000)
출력: 면적/ 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지
풀이
신발끈 공식
N개의 꼭짓점 (x1,y1),(x2,y2),...,(xN, yN)이 반시계/시계 순서로 주어졌을 때
면적 = $|Σ(x_i * y_{i+1}) − Σ(y_i * x_{i+1})| / 2$
/ 마지막은 다시 첫 점과 이어줘야 함
- $y_{N+1} = y_1$
long sum1 = 0;
long sum2 = 0;
for (int i = 0; i < N; i++) {
Point p1 = points.get(i);
Point p2 = points.get((i + 1) % N);
sum1 += (long) p1.x * p2.y;
sum2 += (long) p1.y * p2.x;
}
double area = Math.abs(sum1 - sum2) / 2.0;
코드
import java.io.*;
import java.util.*;
// 다각형의 면적
public class boj_2166 {
static class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
List<Point> points = new ArrayList<>();
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
points.add(new Point(x, y));
}
long sum1 = 0;
long sum2 = 0;
for (int i = 0; i < N; i++) {
Point p1 = points.get(i);
Point p2 = points.get((i + 1) % N);
sum1 += (long) p1.x * p2.y;
sum2 += (long) p1.y * p2.x;
}
double area = Math.abs(sum1 - sum2) / 2.0;
System.out.printf("%.1f\n", area);
}
}728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ/DP+Back-Tracking] 백준 9251 - LCS / 9252 - LCS 2 (Java) (0) | 2025.11.16 |
|---|---|
| [BOJ/DP] 백준 1149 - RGB 거리 / 17404 - RGB 거리 2 (Java) (0) | 2025.11.16 |
| [BOJ/DP] 백준 1106 - 호텔 (Java) (0) | 2025.11.13 |
| [BOJ/Graph] 백준 1707 - 이분 그래프 (Java) (0) | 2025.11.12 |
| [BOJ/DFS+BFS] 백준 14502 - 연구소 (Java) (0) | 2025.11.12 |