none
多边形的点连接最短路径 RRS feed

  • 问题

  • 多边形的点连接最短路径,我的这个有错,暂时找不到出错的原因,请前辈赐教

    Code Snippet

    #include<iostream>
    #include<vector>
    #include<fstream>
    #include<sstream>
    #include<cmath>
    using namespace std;
    //-------------------------------------------------------------------
    typedef vector<int> vint1;
    typedef vector<double> vdouble1;
    typedef vector<vector<int> > vint2;
    //-------------------------------------------------------------------初始化部分
    int main(){
     int x1,y1,x2,y2,x3,y3,x4,y4,address=0,flag=1,count=0;//最短线路地址,标志,判断次数
     double temp=0;//最短线路长度
     vint1 p;
     vdouble1 q;
     vint2 a,b,r[100];
     p.clear(),q.clear(),a.clear(),b.clear();
     for(int i=0;i<100;i++)
      r[i].clear();
     //-------------------------------------------------------------------输入部分
     ifstream in("aaa.txt");
     for(string s;getline(in,s);)
     {
      
      istringstream sin(s);
      for(int i;sin>>i;)
       p.push_back(i);
      a.push_back(p);
     }
     //-------------------------------------------------------------------全部检索不相交线路
     for(unsigned int i=0;i<a.size();i++)
     {
      x1=b[0][0]=a[i][0],y1=b[0][1]=a[i][1];//b用来存储可行性的线路
      for(unsigned int j=i+1;j<a.size();j++)
      {
       x2=b[1][0]=a[j][0],y2=b[1][1]=a[j][1];
       for(unsigned int k=0,m=0,n=1;k<a.size();m+=2,n+=2,k+=2)
       {
        //--------------------------------------------------------------------
        while(m==i || m==j)
         m++;
        x3=b[k+2][0]=a[m][0],y3=b[k+2][1]=a[m][1];
        while(n==i || n==j || n==m)
         n++;
        x4=b[k+3][0]=a[n][0],y4=b[k+3][1]=a[n][1];
        //-------------------------------------------------------------------
        int denom=(x2*y1-x1*y2)*(x4-x3)-(x4*y3-x3*y4)*(x2-x1);
        int assign=(y4-y3)*(x2-x1)-(y2-y1)*(x4-x3);
        double num=denom/assign;
        if(num >= (x1<=x2 ? x1:x2)  && num <= (x1>=x2 ? x1:x2))
        {
         flag=0;
         break;
        }
       }
       if(flag)
       {
        r[count]=b;
        ++count;
       }
      }
     }
     //-------------------------------------------------------------------找出最短线路
     for(unsigned int i=0;i<count;i++)
     {
      for(unsigned int j=0;j<a.size()-1;j++)
       temp+=sqrt(pow((r[i][j][0]-r[i][j+1][0]),2.0)+pow((r[i][j][1]-r[i][j+1][1]),2.0));
      q.push_back(temp);
     }
     temp=q[0];
     address=0;
     for(unsigned int i=0;i<q.size();i++)
      if(temp>=q[i])
      {
       temp=q[i];
       address=i;
      }
     //-------------------------------------------------------------------输出最短线路
     for(unsigned int i=0;i<a.size();++i)
      cout<<r[address][i][0]<<" "<<r[address][i][1]<<endl;
     //-------------------------------------------------------------------
     return 0;
    }

     

     

    2008年11月24日 10:09

答案

全部回复