[Algorithm] 백준 - 2166번 다각형의 면적 (Swift) (CCW 알고리즘)

문제 소개

다각형의 면적을 구하는 문제이다.

문제 풀이

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)))