高考又來了,對於不認真讀書的來講真不是個好消息。為了小楊能在家裡認真讀書,他的親 戚決定駐紮在他的家裡監督他學習,有爺爺奶奶、外公外婆、大舅、大嫂、阿姨......小楊實 在是忍無可忍了,這種生活跟監獄有什麼區別!為了他親愛的小紅,為了他的dota,他決定 越獄!
假設小楊的家是個矩形,左下角座標為(0, 0),右上角座標為(x1, y1)。小楊有n個親戚,駐紮 在矩形裡(位置不同,且不在矩形的邊上)。小楊家裡的每個地方都被親戚監控著,而且只 被距離最近的親戚監控:
也就是說假設小楊所在的位置是(3, 3),親戚A在(3, 0),A與小楊距離是3;親戚B在(6, 7), 則B 與小楊距離是5。距離A< 距離B,所以(3,3)位置由A監控。
如果“最近距離”出現同時有幾個親戚,那麼那個位置同時被那幾個親戚監控。 給出小楊的座標(x0, y0)。因為被發現的人數越少,越獄成功的機會越大,所以小楊需要你
設計一條越獄路線到達矩形的邊上,且被發現的人數最少。 PS:小楊的方向是任意的,也就是說路線上的任意位置只需要是實數。 保證一開始小楊被至多一個親戚監控著。
第一行,一個正整數t<=3,表示測資數目。
接下來t筆測資:
第一行n,表示小楊的親戚個數。 接下來一行四個正整數,表示矩形右上角的座標(x1, y1)和小楊的座標(x0, y0)。 接下來n行,每行兩個正整數,代表一個親戚的位置。
對於每筆測資,輸出一個正整數,表示小楊越獄被發現人數的最小值。