算法設计沙龙--计算几何问题.docVIP

算法设计沙龙---几何算法套餐福州一中程序设计兴趣小组　　你了解几何吗？你了解几何算法吗？我们的沙龙将带领你进入几何的世界，进入计算机处理几何问题的领域。先请你思考以下几个问题，试试看你能否解决？ 　　一、判断点在多边形中的位置　　已知点P的X、Y坐标和一个N边形A1A2…An。判断点P在N边形的内部,外部或边上。　　输入：　　第1行输入N；　　第2行至第N+1行输入N边形各点的X、Y坐标；　　第N+2行输入P点X、Y坐标；　　输出：　　如果在内部，输出NEIBU　　如果在外部，输出WAIBU　　如果在边上，输出BIAN二、Car的旅行路线　　问题描述　　又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。 　　那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。　　任务　　找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。 　　输入文件：键盘输入文件名　　输　　出：到屏幕(输出最小费用，小数点后保留2位。)　　输入格式　　第一行为一个正整数n(0=n=10)，表示有n组测试数据。　　每组的第一行有四个正整数s，t，A，B。　　S(0S=100)表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，　　　(1=A，B=S)。　　接下来有S行，其中第I行均有7个正整数xi1，yi1，xi2，yi2，xi3，yi3，Ti，这当中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分别是第I个城市中任意三个机场的坐标，T I为第I个城市高速铁路单位里程的价格。　　输出格式　　共有n行，每行一个数据对应测试数据。 　　样例输入　　1　　1 10 1 3　　1 1 1 3 3 1 30　　2 5 7 4 5 2 1　　8 6 8 8 11 6 3　　样例输出　　47.55 三、无线电测向　　问题描述：　　一艘有天线定位装置的船能通过接收当地灯塔信号来确定自己的位置。每个灯塔固定在已知点上并发出特有的信号。当船检测到信号，它可通过旋转天线直到信号达到最大强度。这样就可确定自身与该灯塔的位置关系。只要接收到两个灯塔的信息，就有可能确定船当前的位置。 　　编程任务：　　通过一对灯塔信息来确定船的位置。　　灯塔和船的位置被确定在一个直角坐标系内。X轴正向指向东，Y轴正向指向北。船的航行路线从正北开始按顺时针用度表示。北是0°，东是90°，南是180°，西是270°。灯塔与船的位置关系用相对于船的航行方向顺时针用度表示。　　数据输入：输入数据由文件名为INPUT.TXT的文本文件提供。文件的第一行是一个整数，表示灯塔的数目N(N=30)。以下N行,每行表示一个灯塔,为灯塔名称（名称是20个以下的字母），X坐标和Y坐标。它们都用空格隔开。　　灯塔信息下面是船的信息包括三行，一行是船的方向，其余两行是所接收到的灯塔信号。　　具体如下：　　输入数据　　　　　　　　　　数据的含义　　方向　 　 　　　　　　　　　船的航行方向； 　　名称１　角度１　　　　　　　第一个灯塔信息的名称，灯塔的方位；　　名称２　角度２　　　　　　　第二个灯塔信息的名称，灯塔的方位。　　灯塔的方位为船与灯塔所在的直线与船的航行方向的夹角（从船的航行方向开始顺时针，角度1=角度1+180）。2个数据用空格隔开。　　数据输出：将船的位置（精确到２位小数）。输出到OUTPUT.TXT文件中。如果无法确定船的位置，应输出NO ANSWER（不能使用小写）。　　输入文件示例　　5　　a 1 5　　b 1 1000　　c 2 4　　d 51 60　　e 153 79　　30　　e 160　　d 210 　　输出 　　160.83 123.41 四、监视摄像机　　[问题描述]　　一个著名的仓库管理公司SERKOI请你为其安装一套闭路监视系统，由于SERKOI财力有限，每个房间只能安装一台摄像机，不过其镜头可以向任何方向转换。　　请你写一个程序，对于给定的房间示意图，判断是否有可能在这个房间中的某一位置安置一台摄像机，使其能监视到房间的每一个角落。　　[输入格式]　　第一行是一个整数n（4=n=100），表示房间的示意图是一个n边形。以下n行，每一行给出一个顶点的坐标（xn,yn）。　　[输