[Tyvj 1612]放置镜子

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 race.in 输出文件 race.out

背景 Background 
   百度NOIP吧成功举办了五子棋比赛之后，吧主又准备开始智力比赛 
描述 Description  
   比赛是这样的，有一束光从一个点射入，你可以调整光射入的方向。比赛中可以放置一些镜子来改变光路，使得光通过某一个点，并要求光走过的距离最短。需要注意的是，你必须保证任何时刻光都是沿着正东、正西、正南、正北方向走。
看到这个题目，吧友们都说太简单了，于是准备加大难度，只允许在N个地方放置镜子（也可以不放置）。你的任务就是要找到这个最短距离，并输出它。
 
输入格式 Input Format 
   第一行输入一个整数N，表示一共有N个位置可以放置镜子
接下来有N+2行，第2行为起点的坐标，第N+3行是终点的坐标，第3行到第N+2行为可以放置镜子的坐标，坐标均为整数。
 
 输出格式 Output Format 
   只有一行，输出光走过的最短路径，并保留3位小数。如果无论怎么样，都无法到达终点，则输出“NO”.”
【输入样例1】
2
0 0
1 1
0 1
1 -1
【输出样例1】
4.000

【输入样例2】
2
0 0
1 1
0 1
2 2

【输出样例2】
NO

时间限制 Time Limitation 
   各个测试点1s
 
【数据范围】
对于10%的数据 满足N=0
对于30%的数据 满足N<=1
对于60%的数据 满足N<=1000
对于100%的数据 满足N<=100000 所有坐标范围的绝对值<=2*10^9