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

3G开发

开发平台:

Visual C++

  1. #include<iostream>
  2. #include<cmath>
  3. #include<stdlib.h>
  4. #include<time.h>
  5. using namespace std;
  6. const double pi=3.1415926;
  7. struct node{double x,y,wucha,w;int ok;}a[111],a1[111];
  8. struct node2{int n1,n2,n3;double w;}d[3333],o;
  9. double e[111][111],totw;
  10. bool c[111][111];
  11. int n,l,v,m,p,q,i,j,chang,kuan;
  12. double wucha,totwc;
  13. double maxvalue(double x,double y);
  14. double minvalue(double x,double y);
  15. double maxvalue(double x,double y)
  16. {
  17. return (x>y?x:y);
  18. }
  19. double minvalue(double x,double y)
  20. {
  21. return (x>y?y:x);
  22. }
  23. int jiefangcheng(int i0,int i1,int i2,int i3,double w){
  24.   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;
  25.   if(e[i1][i2]+e[i2][i0]<e[i1][i0])return 0;
  26.   p=2*(a[i2].x-a[i1].x);
  27.   q=2*(a[i2].y-a[i1].y);
  28.   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;
  29.   if(abs(p)<1e-6){
  30.     y2=y1=o/q;
  31.     t1=1;
  32.     t2=-2*a[i1].x;
  33.     t3=a[i1].x*a[i1].x-e[i0][i1]*e[i0][i1]+(y1-a[i1].y)*(y1-a[i1].y);
  34.     if(t2*t2-4*t1*t3<-1e-6)return 0;
  35.     x1=(-t2+sqrt(t2*t2-4*t1*t3))/2/t1;
  36.     x2=(-t2-sqrt(t2*t2-4*t1*t3))/2/t1;
  37.     }else{
  38.     t1=q*q/p/p+1;
  39.     t2=-2*o*q/p/p+2*a[i1].x*q/p-2*a[i1].y;
  40.     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];
  41.     if(t2*t2-4*t1*t3<-1e-6)return 0;
  42.     y1=(-t2+sqrt(t2*t2-4*t1*t3))/2/t1;
  43.     y2=(-t2-sqrt(t2*t2-4*t1*t3))/2/t1;
  44.     x1=(o-q*y1)/p;
  45.     x2=(o-q*y2)/p;
  46.     }
  47.   d1=(x1-a[i3].x)*(x1-a[i3].x)+(y1-a[i3].y)*(y1-a[i3].y);
  48.   d2=(x2-a[i3].x)*(x2-a[i3].x)+(y2-a[i3].y)*(y2-a[i3].y);
  49.   d3=e[i0][i3]*e[i0][i3];
  50.   if(abs(d1-d3)<abs(d2-d3)){x=x1;y=y1;}else{x=x2;y=y2;}
  51.   a1[i0].x+=w*x;
  52.   a1[i0].y+=w*y;
  53.   a1[i0].w+=w;
  54.   ++a1[i0].ok;
  55.   return 1;
  56. }
  57. void calw(){
  58.   int i,j,k;
  59.   double p,a1,a2,a3,dis1,dis2,dis3,mn,mx;
  60.   for(i=1;i<=m-2;i++)
  61.     for(j=i+1;j<=m-1;j++)
  62.       for(k=j+1;k<=m;k++){
  63.         ++l;
  64.         d[l].n1=i;d[l].n2=j;d[l].n3=k;
  65.         dis1=e[i][j];
  66.         dis2=e[i][k];
  67.         dis3=e[j][k];
  68.         a1=acos((dis1*dis1-dis2*dis2-dis3*dis3)/2/dis2/dis3);
  69.         a2=acos((dis2*dis2-dis1*dis1-dis3*dis3)/2/dis1/dis3);
  70.         a3=acos((dis3*dis3-dis2*dis2-dis1*dis1)/2/dis2/dis1);
  71.         mn=minvalue(minvalue(a1,a2),a3);
  72.         mx=maxvalue(maxvalue(a1,a2),a3);
  73.         d[l].w=1-(mx-mn)/pi;
  74.         }
  75.         
  76.   for(i=1;i<=l;i++)
  77.     for(j=i+1;j<=l;j++)if(d[i].w<d[j].w){o=d[i];d[i]=d[j];d[j]=o;}
  78.   if(20>l)v=l;else v=20;
  79.   totw=0;
  80.   for(i=1;i<=v;i++){
  81.     if(d[i].w>1e-3){
  82.       totw+=d[i].w;
  83.     }else 
  84.     --v;
  85.     }
  86. }
  87. void cal(int k){
  88.   int i,j,l,tmp;
  89.   for(i=1;i<=v;i++){
  90.     if(e[d[i].n1][k]<e[d[i].n2][k])swap(d[i].n1,d[i].n2);
  91.     if(e[d[i].n2][k]<e[d[i].n3][k])swap(d[i].n2,d[i].n3);
  92.     if(e[d[i].n1][k]<e[d[i].n2][k])swap(d[i].n1,d[i].n2);
  93.     //n1,n2,n3按与k的距离从大到小排序 
  94.     
  95.     if(jiefangcheng(k,d[i].n1,d[i].n2,d[i].n3,d[i].w));else 
  96.     if(jiefangcheng(k,d[i].n1,d[i].n3,d[i].n2,d[i].w));else 
  97.     if(jiefangcheng(k,d[i].n2,d[i].n3,d[i].n1,d[i].w));
  98.     
  99. //    jiefangcheng(k,d[i].n1,d[i].n2,d[i].n3);
  100.     }
  101.   
  102.    a1[k].x=a1[k].x/a1[k].w;
  103.    a1[k].y=a1[k].y/a1[k].w;
  104.    //a1[k].x=a1[k].x/v;
  105.    //a1[k].y=a1[k].y/v;
  106.   //解得未知点为a1[k]   
  107. }
  108. int main(){
  109.   srand(time(0));
  110.   printf("请输入总节点个数,基站个数,误差值:");
  111.   cin>>n>>m>>wucha;//m为基站个数 
  112.   printf("请输入网络区域的长、宽:");
  113.   cin>>chang>>kuan;
  114.   ++chang;++kuan;
  115.   freopen("output3.txt","w",stdout);
  116. //m=10;wucha=0.3;
  117.   for(i=1;i<=n;i++){
  118.     while(1){
  119.       p=rand()%chang;
  120.       q=rand()%kuan;
  121.       if(c[p][q]==0){
  122.         c[p][q]=1;
  123.         break;
  124.         }
  125.       }
  126.     a[i].x=p;
  127.     a[i].y=q;  
  128.     }
  129.   for(i=1;i<=n;i++)
  130.     for(j=1;j<=n;j++)
  131.       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;
  132.   calw();
  133.   
  134.   for(i=m+1;i<=n;i++)cal(i);
  135.   
  136.   for(i=m+1;i<=n;i++)if(a1[i].ok>0)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));
  137.   for(i=m+1;i<=n;i++)if(a1[i].ok>0)totwc+=a1[i].wucha;
  138.   
  139.   printf("总误差:      "); 
  140.   cout<<totwc<<endl;
  141.    for(i=1;i<=m;i++)
  142.   a1[i].ok=1;
  143.  // for(i=m+1;i<=n;i++)if(a1[i].ok){
  144.    for(i=1;i<=n;i++)if(a1[i].ok){
  145.     //printf("第%d个点的原始坐标:          ",i);
  146.     cout<<a[i].x<<' '<<a[i].y<<' '<<a1[i].x<<' '<<a1[i].y<<' '<<a1[i].wucha<<endl;
  147.     //printf("算出的第%d个点的坐标和误差:  ",i);
  148.     //cout<<a1[i].x<<' '<<a1[i].y<<' '<<a1[i].wucha<<endl;
  149.     }else cout<<"Cannot Find."<<endl;
  150.   
  151.   return(0); 
  152. }