本文主要是介绍极角排序:POJ 1696(叉积+深搜），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
POJ1696题意：一只很特殊的蚂蚁，只能向坐转，并且不能经过已经走过的路。一张地图上有n个食物让蚂蚁去采集，求蚂蚁经过所有食物的顺序(找出一条最长的非右拐的路径)。
样例：
Sample Input
2 （二次测试）
10 （十个食物点）
1 4 5 （点的编号，x坐标，y坐标)
2 9 8
3 5 9
4 1 7
5 3 2
6 6 3
7 10 10
8 8 1
9 2 4
10 7 6
14
1 6 11
2 11 9
3 8 7
4 12 8
5 9 20
6 3 2
7 1 6
8 2 13
9 15 1
10 14 17
11 13 19
12 5 18
13 7 3
14 10 16
Sample Output
10 8 7 3 4 9 5 6 2 1 10
14 9 10 11 5 12 8 7 6 13 4 14 1 3 2
分析：
每次找到一个基准点p0，最开始的时候是最左下角的点,然后我们再从未访问的点中找到相对于p0最小极角的那个点，比较极角用叉积来计算，每次迭代总是用此次循环中找到的最小极角来代替p0,然后再以这个新的p0,找到剩下的点中的最小极角，这样我们找到的就是一条最大的不右转的路径了。
下面是AC过的代码：
Java代码 
- import java.util.Scanner;
- import java.util.Arrays;
- class point implements Comparable {
- int id ;//食物原始的编号
- int ord ;//蚂蚁经过的顺序
- double x;//食物的x坐标
- double y;//食物的y坐标
- public int compareTo(Object o) {//升序排列
- return this.ord - ((point) o).ord;
- }
- }
- public class Main{
- point[] p;//所有的食物点
- boolean vis[] ;//标记是否被蚂蚁吃过了
- int n ;//食物的个数
- public Main(){
- }
- //向量(x1,y1),(x2,y2)的叉积
- public double det(double x1,double y1,double x2,double y2){
- return x1*y2 - x2*y1;
- }
- //小于0,说明向量ab的极角大于ac的极角
- double cross(point a,point b,point c){
- return det(b.x - a.x, b.y - a.y, c.x - a.x,c.y - a.y);
- }
- //求距离
- double dis(point a,point b) {
- double x1 = a.x;
- double y1 = a.y;
- double x2 = b.x;
- double y2 = b.y ;
- return (x2 - x1 )*(x2 - x1) + (y2-y1)*(y2 - y1);
- }
- //pre:蚂蚁开始的位置，num：蚂蚁经过的顺序
- void dfs(int pre,int num){
- if(num == n) return ;
- int mi = 1;
- while(vis[mi]) mi++;//找一个没有被蚂蚁吃过的点
- //在没有吃完的点中找出极角最小的点
- for(int i = mi + 1 ;i <= n;i++){
- if(vis[i]) continue ;//再找一个没有被蚂蚁吃过的点
- double w = cross(p[pre],p[mi],p[i]);//计算叉积
- if(w < 0) mi = i;//记录极角小的那个点,极角相同取距离近的点
- if((w ==0) && dis(p[pre],p[i]) < dis(p[pre],p[mi])) mi = i;
- }
- p[mi].ord = num + 1;//记录吃的顺序
- vis[mi] = true ;//标记为已吃过
- dfs(mi,num + 1) ;//递归
- }
- public static void main(String args[]){
- Main ma=new Main();
- ma.go();
- }
- public void go(){
- Scanner in=new Scanner(System.in);
- int t;
- t=in.nextInt();
- while(t-->0){
- n=in.nextInt();
- int mi = 1 ;
- vis=new boolean[n+1];
- p=new point[n+1];
- p[0]=new point();//这个点无用。
- for(int i = 1 ; i<= n;i++){//从命令行输入食物信息
- p[i]=new point();
- p[i].id=in.nextInt();//食物的编号
- p[i].x=in.nextDouble();//x坐标
- p[i].y=in.nextDouble(); //y坐标
- //找y最小的食物点,也即蚂蚁应该第一个吃的点
- if(p[mi].y > p[i].y)
- mi = i;
- }
这篇关于极角排序:POJ 1696(叉积+深搜）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
