test1.cpp
上传用户:vipking888
上传日期:2015-02-03
资源大小:93k
文件大小:3k
源码类别:

3G开发

开发平台:

Visual C++

  1. #include<iostream>
  2. #include<cmath>
  3. #include<time.h>
  4. using namespace std;
  5. struct node{double x,y,wucha;bool ok;}a[111],a1[111];
  6. bool c[111][111];
  7. int i,j,n,m,s,p,q,k,chang,kuan;
  8. double totwc,wucha,e[111][111];
  9. int jiefangcheng(int i0,int i1,int i2,int i3){
  10.   double d1,d2,d3,y1,y2,x1,x2,t1,t2,t3,t4,o,x,y,a11,a12,a21,a22,zhi,p,q,b11,b12,b21,b22;
  11.   if(e[i1][i2]+e[i2][i0]<e[i1][i0])return 0;
  12.   p=2*(a[i2].x-a[i1].x);
  13.   q=2*(a[i2].y-a[i1].y);
  14.   o=e[i0][i1]*e[i0][i1]-e[i0][i2]*e[i0][i2]-a[i1].x*a[i1].x+a[i2].x*a[i2].x-a[i1].y*a[i1].y+a[i2].y*a[i2].y;
  15.   if(abs(p)<1e-6){
  16.     y2=y1=o/q;
  17.     t1=1;
  18.     t2=-2*a[i1].x;
  19.     t3=a[i1].x*a[i1].x-e[i0][i1]*e[i0][i1]+(y1-a[i1].y)*(y1-a[i1].y);
  20.     if(t2*t2-4*t1*t3<-1e-6)return 0;
  21.     x1=(-t2+sqrt(t2*t2-4*t1*t3))/2/t1;
  22.     x2=(-t2-sqrt(t2*t2-4*t1*t3))/2/t1;
  23.     }else{
  24.     t1=q*q/p/p+1;
  25.     t2=-2*o*q/p/p+2*a[i1].x*q/p-2*a[i1].y;
  26.     t3=o*o/p/p+a[i1].x*a[i1].x-2*a[i1].x*o/p+a[i1].y*a[i1].y-e[i0][i1]*e[i0][i1];
  27.     if(t2*t2-4*t1*t3<-1e-6)return 0;
  28.     y1=(-t2+sqrt(t2*t2-4*t1*t3))/2/t1;
  29.     y2=(-t2-sqrt(t2*t2-4*t1*t3))/2/t1;
  30.     x1=(o-q*y1)/p;
  31.     x2=(o-q*y2)/p;
  32.     }
  33.   d1=(x1-a[i3].x)*(x1-a[i3].x)+(y1-a[i3].y)*(y1-a[i3].y);
  34.   d2=(x2-a[i3].x)*(x2-a[i3].x)+(y2-a[i3].y)*(y2-a[i3].y);
  35.   d3=e[i0][i3]*e[i0][i3];
  36.   if(abs(d1-d3)<abs(d2-d3)){x=x1;y=y1;}else{x=x2;y=y2;}
  37.   a1[i0].x=x;
  38.   a1[i0].y=y;
  39.   a1[i0].ok=1;
  40.   return 1;
  41. }
  42. void cal(int k){
  43.   int i,j,p,b[5],tmp=0;
  44.   bool c[111],hasans=0;
  45.   while(1){
  46.     ++tmp;
  47.     memset(c,0,sizeof(c));
  48.     for(i=1;i<=3;i++){
  49.       while(1){p=rand()%m+1;if(c[p]==0){c[p]=1;break;}}    
  50.       b[i]=p;
  51.       }
  52.     for(i=1;i<=3;i++)for(j=i+1;j<=3;j++)if(e[b[i]][k]<e[b[j]][k]){p=b[i];b[i]=b[j];b[j]=p;}
  53.     if(jiefangcheng(k,b[1],b[2],b[3])){hasans=1;break;}else 
  54.     if(jiefangcheng(k,b[1],b[3],b[2])){hasans=1;break;}else 
  55.     if(jiefangcheng(k,b[2],b[3],b[1])){hasans=1;break;}
  56.     if(tmp>10)break; 
  57.   }
  58.   
  59. }
  60. int main(){
  61.   
  62.   srand(time(0));
  63.   printf("请输入总节点个数,基站个数,误差值:");
  64.   cin>>n>>m>>wucha;//m为基站个数 
  65.   printf("请输入网络区域的长、宽:");
  66.   cin>>chang>>kuan;
  67.   ++chang;++kuan;
  68.   freopen("output1.txt","w",stdout);
  69. //m=10;wucha=0.3;
  70.   for(i=1;i<=n;i++){
  71.     while(1){
  72.       p=rand()%chang;
  73.       q=rand()%kuan;
  74.       if(c[p][q]==0){
  75.         c[p][q]=1;
  76.         break;
  77.         }
  78.       }
  79.     a[i].x=p;
  80.     a[i].y=q;  
  81.     }
  82.     
  83. //a[1].x=41;a[1].y=85;a[2].x=72;a[2].y=38;a[3].x=80;a[3].y=69;a[4].x=96;a[4].y=22;
  84.   for(i=1;i<=n;i++)
  85.     for(j=1;j<=n;j++)
  86.       e[i][j]=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y))+wucha*10;
  87.   for(i=m+1;i<=n;i++)cal(i);
  88.   
  89.   
  90.   
  91. //  for(i=1;i<=n;i++)cout<<a[i].x<<' '<<a[i].y<<endl;
  92.   
  93.   for(i=m+1;i<=n;i++)if(a1[i].ok)a1[i].wucha=sqrt((a1[i].x-a[i].x)*(a1[i].x-a[i].x)+(a1[i].y-a[i].y)*(a1[i].y-a[i].y));
  94.   for(i=m+1;i<=n;i++)if(a1[i].ok)totwc+=a1[i].wucha;
  95.   printf("总误差:      "); 
  96.   cout<<totwc<<endl;
  97.   for(i=1;i<=m;i++)
  98.   a1[i].ok=1;
  99.  // for(i=m+1;i<=n;i++)if(a1[i].ok){
  100.   for(i=1;i<=n;i++)if(a1[i].ok){
  101.     //printf("第%d个点的原始坐标:          ",i);
  102.     cout<<a[i].x<<' '<<a[i].y<<' '<<a1[i].x<<' '<<a1[i].y<<' '<<a1[i].wucha<<endl;
  103.     //printf("算出的第%d个点的坐标和误差:  ",i);
  104.     //cout<<a1[i].x<<' '<<a1[i].y<<' '<<a1[i].wucha<<endl;
  105.     }else cout<<"Cannot Find."<<endl;
  106.   
  107.   return(0); 
  108. }