首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C++ >

分治法,最短点距解决方案

2012-02-23 
分治法,最短点距要求是:输入由若干组测试数据组成。每组数据的第1行包含一正整数N(2≤N≤100000),代表场地中

分治法,最短点距
要求是:
输入由若干组测试数据组成。
每组数据的第1行包含一正整数N(2≤N≤100000),代表场地中玩具的个数。接下来有N行输入,每行包含一个玩具的x和y坐标。当N为0时,表示全部测试结束,不要对该数据做任何处理。
输出要求:
对每一组测试,在一行里输出符合设计要求的套圈的半径,精确到小数点后两位。

用VC6.0编译时,出现类似的错误:
error C2676: binary '[' : 'point' does not define this operator or a conversion to a type acceptable to the predefined operator
请帮忙修改一下。


#include <iostream>
#include <cmath>
#include <fstream>
#include <cctype>
#include <iomanip>
#include <cstdio>
#include <fstream>
using namespace std;

ifstream fi("input.txt");
ofstream fo("output.txt");

  typedef struct {  
  int x;  
  int y;  
  } point;  
int the_nearest_distance(point* s,int n); //求左右两边的最小距离
void BubbleSortx(point* r,int n) ; //对点按X值排序
void BubbleSorty(point* r,int n); //对点按Y值排序
int distance(point a, point b); //求两点的距离
int main() 
{
  int i,j,k,n;
   
  point coor[100];
  fi >> i;
  n=i;
for (int t=1;t<=i;t++)
{
fi>>j;  
if (fi.fail() ) //输入判断
{cout<<"第"<<i+1<<"行第一个输入有错,请输入数字"<<endl;
break;
}
fi>>k;
if(fi.fail())
{cout<<"第"<<i+1<<"行第二个输入有错,请输入数字"<<endl;
break;
}
if(t!=i)
{getchar();//须按回车键结束,不是任意键
  cout<<"按回车键结束";
return 0;}
else 
{ coor[t].x=j;
coor[t].y=k;
}
}
int Min;
  Min=the_nearest_distance(coor,i);


fi.close();



  fo<<setprecision(3)<<setiosflags(ios::fixed|ios::showpoint)<<Min<<endl;
cout<<setprecision(3)<<setiosflags(ios::fixed|ios::showpoint)<<Min<<endl;


}



int the_nearest_distance(point s,int n) //the_nearest_distance函数定义
{ BubbleSortx( &s,n ); //对点按X值排序 

  int dis,mid,leftmin,rightmin,midmin;
if(n==2)
  { dis=distance(s[0],s[1]);}
  else if(n==1)
  {dis=999999999;}
  else mid =n/2;
  leftmin=the_nearest_distance( s, mid);
  rightmin=the_nearest_distance(&s[mid],mid);
  midmin=leftmin<rightmin?leftmin:rightmin;

BubbleSorty( &s,n ); //对点按Y值排序
  int crossmin=99999999;
  for(int m=0;m<=n/2;m++) //两个for循环是对分属两边的点找出可能最近的点
if( s[m].x-s[n/2].x<midmin)//到分线距离小于已知两边的最小
{ for(int p=n/2;p<n;p++)  
  {int tag=0;
  if(tag<6) //最多比较6个点
  if((s[m].y-s[p].y)<2*midmin)
  {
  dis=distance(s[m],s[p]);
  crossmin=dis<crossmin?dis:crossmin;
  tag++;}
   
break;}}
else break;
 
  return midmin<crossmin?midmin:crossmin;
  
};
void BubbleSortx(point* r,int n)
{
  int i, j, flag; //当flag为0则停止排序
  point temp;
  for ( i=1; i<n; i++) { //i 表示趟数,最多n-1趟
  flag=0; //开始时元素未交换
  for ( j=n-1; j>=i; j--) { 
  if (r[j].x<r[j-1].x) { //发生逆序 
  temp=r[j]; r[j]=r[j-1]; r[j-1]=temp;
  flag=1; //交换,并标记发生了交换
  }
  }  
  if(flag==0) break;
  }
};

void BubbleSorty(point* r,int n)
{
  int i, j, flag; //当flag为0则停止排序


  point temp;
  for ( i=1; i<n; i++) { //i 表示趟数,最多n-1趟
  flag=0; //开始时元素未交换
  for ( j=n-1; j>=i; j--) { 
  if (r[j].y<r[j-1].y) { //发生逆序 
  temp=r[j]; r[j]=r[j-1]; r[j-1]=temp;
  flag=1; //交换,并标记发生了交换
  }
  }  
  if(flag==0) break;
  }
};
int distance (point a,point b)
{ int d,xx,yy;
xx=a.x-b.x;
yy=a.y-b.y;
 d=sqrt(xx*xx+yy*yy);
 return d;
}
 

[解决办法]
int the_nearest_distance(point s,int n) //the_nearest_distance函数定义
{ BubbleSortx( &s,n ); //对点按X值排序

int dis,mid,leftmin,rightmin,midmin;
if(n==2)
{ dis=distance(s[0],s[1]);}
....

 传进来的是一个point的变量,不是数组,point结构也没有重载[],这么访问 distance(s[0],s[1]不行的

[解决办法]
int the_nearest_distance(point &s,int n) 
这样呢??

热点排行