백준 [2166] kotlin

문제

https://www.acmicpc.net/problem/2166

2166번: 다각형의 면적

풀이

CCW 알고리즘 사용해서 해결한 문제이다.

 

세 점 A(x1, y1) B(x2,y2) C(x3,y3) 이 있을 때 삼각형의 넓이는 다음과 같다.

0.5(abs((x1y2 + x2y3 + x3y1) - (y1x2 + y2x3 + y3x1))

 

이는 CCW 알고리즘의 결과에 0.5를 곱해준 것과 같다.

 

좌표 하나를 기준으로 삼각형을 만들어 각 삼각형의 합을 구해주면 된다.

 

코드

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.abs

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))

    var N = br.readLine().toInt()

    var polygon = mutableListOf<Pair<Double, Double>>()
    repeat(N)
    {
        val tmp = br.readLine().split(" ").map { it.toDouble() }
        polygon.add(Pair(tmp[0], tmp[1]))
    }

    var answer = 0.0
    for(i in 1 until N-1){
        answer += ccw(polygon[0], polygon[i], polygon[i+1])
    }

    bw.write(String.format("%.1f", abs(answer)))
    bw.flush()
    bw.close()
}

fun ccw(standard : Pair<Double, Double>, a : Pair<Double, Double>, b : Pair<Double, Double>) : Double
{
    return ((standard.first * a.second + a.first * b.second + b.first * standard.second) - (standard.first * b.second + standard.second * a.first + a.second * b.first)) * 0.5
}