백준 2166 다각형의 면적
23 Jun 2021https://www.acmicpc.net/problem/2166
n개의 점으로 이루어진 다각형의 면적을 구하는 문제이다.
다각형을 한점을 중심으로 선분을 그어서 삼각형 형태로 나누면 각각의 삼각형의 넓이를 모두 구하면 다각형의 면적을 구할 수 있다. 놀랍게도 외적은 두 벡터로 이루어진 삼각형의 넓이의 2배와 같다. 이를 이용해서 다각형의 면적을 구한다.
다만 위의 그림처럼 외적 값이 음수가 나타나는 경우가 있다. 하지만 두번째 삼각형의 빨간 부분에서 세번째 삼각형의 빨간 부분을 빼면 우리가 구하고자 하는 다각형의 넓이를 구할 수 있다는 것을 볼 수 있다. 실제로 외적값이 음수가 나오는 경우는 빼줘야하는 부분에 해당하기 때문에 이를 고려해서 연산하면 된다.
- 전체 코드
import Foundation
func ccw(x1: Int, x2: Int, x3: Int, y1: Int, y2: Int, y3: Int, z1: Int, z2: Int, z3:Int) -> (Int, Int, Int){
let A = (x:x2-x1, y:y2-y1, z:z2-z1)
let B = (x:x3-x1, y:y3-y1, z:z3-z1)
let AxB = (A.y*B.z - A.z*B.y, A.z*B.x - A.x*B.z, A.x*B.y - A.y*B.x)
return AxB
}
let n = Int(readLine()!)!
var point:[(Int, Int, Int)] = []
for _ in 1...n {
let line = readLine()!.split(separator: " ").map{Int(String($0))!}
point.append((line[0], line[1], 0))
}
let A = point[0]
var result:Double = 0
for i in 1..<n-1 {
let B = point[i], C = point[i+1]
let calculate = ccw(x1: A.0, x2: B.0, x3: C.0, y1: A.1, y2: B.1, y3: C.1, z1: A.2, z2: B.2, z3: C.2)
result += Double(calculate.2)
}
result = abs(result)/2
print(String(format: "%.1f", result))