[ 백준 2166 ] - 다각형의 면적(Kotlin)

 

 

2166번: 다각형의 면적

 

문제 이해 & 기본 개념

• n개의 점으로 이루어진 다각형의 넓이를 구하는 문제
• 신발끈 공식을 이용하면 쉽게 풀 수 있다.

---

중요 포인트

• N이 최대 10,000까지, 각 좌표의 절댓값이 최대 100,000이므로 Long 타입을 선택해야 한다.
• 신발끈 공식에서는 좌표를 이어지도록 나열하는 것이 중요한데, 해당 문제에서는 다각형을 이루는 순서대로 입력이 들어온다.
• 만약, 순서가 랜덤이라면 하나의 다각형으로 고정 되지 않기에 문제가 성립되지 않는다.
  • 스페셜 저지면 가능하겠지만, 일반 문제이기 때문에 성립 x

---

주의 할 점

• 문제 조건 중 소수점 아래 둘째 자리에서 반올림하여 첫째 자리에서 출력한다. 라는 조건이 있다.
• Double  타입을 사용했을 때 아래와 같이 출력된다.

5
-100000 100000
-100000 -100000
100000 -100000
100000 99999
99999 100000

출력 : 3.9999999910E5
정답 : 39999999999.5

 

• 출력 형식이 달라서 틀린건 지, 부동 소수점 방식으로 인한 오차 때문인 지는 잘 모르겠다.
• 그래서 Double을 쓰지 않고 푸는 것이 중요하다.

 

최종 풀이

• 신발끈 공식을 그대로 적용해주면 된다.
• 신발끈 공식에서 합을 구한 후 2로 나눈 값이 다각형의 넓이가 된다.
• 2로 나눈 다는 것은 소수점 첫 째 자리가 0 아니면 5라는 소리이다.
• 따라서, 비트 연산을 이용하면 소수점 첫 째 자리를 쉽게 구할 수 있다.

    val result = abs((xSum - ySum))
    // result shr 1 == result >> 1 == result / 2
    // result and 1 => 맨 끝자리 비트가 1인지 보는 것
    return "${result shr 1}.${(result and 1) * 5}"

 

---

 

소스 코드

package Gold.BOJ2166

import kotlin.math.abs

fun solve(list:ArrayList<Pair<Long,Long>>, n:Int):String{
    list.add(list[0])

    var xSum:Long = 0
    var ySum:Long = 0
    for (i in 0 until n){
        xSum += list[i].first * list[i+1].second
        ySum += list[i].second * list[i+1].first
    }

    val result = abs((xSum - ySum))
    return "${result shr 1}.${(result and 1) * 5}"
}

fun main(){
    val n = readln().toInt()
    val list = arrayListOf<Pair<Long,Long>>()

    repeat(n){
        list.add(
            readln().split(" ").map { it.toLong() }.let { Pair(it[0], it[1]) })
    }

    println(solve(list,n))
}