极角排序: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过的代码：

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;
    }
      vis[mi] = true;//蚂蚁最先吃的食物点
      p[mi].ord = 1 ;//蚂蚁经过的顺序为1
      dfs(mi,1);//从这点开始深搜
      Arrays.sort(p);//全部解决，按蚂蚁经过的顺序排序所有点
      System.out.printf("%d",n);
       for(int i = 1;i <=n;i++){
          System.out.printf(" %d",p[i].id) ;
        }
       System.out.println();
   }
 }
}

源码下载：