轉站通知

本站已停止更新!!想繼續收看我的新文章的話,請前往我的新Blog - Chino's

2014年3月13日 星期四

HOJ::Problem : 24 - 阿里不達轟

http://hoj.twbbs.org.tw/judge/problem/view/24
這題是NPSC國中組出賽題。給你炸彈的座標、半徑和敵人的座標、半徑,只要兩圓有碰到就算攻擊的到敵人,問最少要幾顆炸彈。

這題因為範圍很小,直接暴搜就好。判斷兩圓有沒有碰到的方法,我是用兩點的距離平方(直角三角形)和半徑和的平方做比較。
我用一個整數紀錄一個炸彈可以炸到哪幾個敵人(2進位一位代表一個敵人),DFS時就用OR運算,只要全部都炸的到就回傳炸彈數(要多少才算全部炸到我先預處理了)。
要是跑完了都炸不到就輸出Impossible。