→ Problems
[Algorithm] 백준 - 2166번 다각형의 면적 (Swift) (CCW 알고리즘)
Swift librarian
2024. 6. 17. 10:19
문제 소개
다각형의 면적을 구하는 문제이다.

문제 풀이
CCW 알고리즘
이 문제는 CCW(Count Clockwise) 알고리즘을 사용했다. 단순히 정답만 궁금하다면 아래 정답코드를 참고하면 된다. 기하학이 나와서 문제가 골드인데 사실 공식만 안다면 단순한 구현문제이다. 솔직히 벡터의 외적을 사용하지 않고 이 문제를 쉽게 푸는 방법을 모르겠다...

두 백터의 외적을 통해 벡터가 시계방향인지, 반시계방향인지 판별할 수 있는데, 아래의 코드로 CCW 를 구현할 수 있다.
func ccw(_ A: Point, _ B: Point, _ C: Point) -> Int {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x)
}
이 벡터의 외적을 2로 나눈 후 절댓값이 넓이가 된다. 이를 활용하여 코드를 작성하면 된다.
정답 코드
import Foundation
let n = Int(readLine()!)!
struct Point {
var x: Int
var y: Int
}
func ccw(_ A: Point, _ B: Point, _ C: Point) -> Int {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x)
}
var points: [Point] = []
for _ in 0..<n {
let xy = readLine()!.split(separator: " ").map { Int($0)! }
let point = Point(x: xy[0], y: xy[1])
points.append(point)
}
var answer = 0.0
for i in 1..<n-1 {
answer += Double(ccw(points[0], points[i], points[i+1]))/2
}
print(String(format: "%.1f" , abs(answer)))