最近点对.rar

/*#include <iostream> #include <algorithm rel='nofollow' onclick='return false;'> #include <cmath> #define INF 0x6FFFFFFF using namespace std; struct Node{ double x, y; friend bool operator < (const Node &a, const Node &b){ if(a.x == b.x) return a.y < b.y; return a.x < b.x; } }; Node* Point = NULL; double _distance(const Node a, const Node b) { return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); } double smaller(double p, double q) { return (p > q) ? q : p; } double Closest_distance(int left, int right) { double d = INF; double distance_tmp; if(left == right) return 0; if(right == left+1) return _distance( Point[left], Point[right] ); int mid = (left + right) / 2; d = smaller( Closest_distance(left,mid) , Closest_distance(mid,right) ); for(int i=mid-1; i>=left && Point[mid].x - Point[i].x < d; i--){ for(int j = mid+1; j<=right && Point[j].x - Point[mid].x < d && fabs( Point[i].y - Point[j].y) < d; j++){ distance_tmp = _distance( Point[i], Point[j] ); if(distance_tmp < d) d = distance_tmp; } } return d; } int main() { int n; cout<<"输入点对个数："<<endl; cin>>n; cout<<"输入点对坐标"<<endl; Point = new Node[n]; for(int i=0; i<n ; i++){ cin>>Point[i].x>>Point[i].y; } sort(Point,Point+n); cout<<"最近距离为："<<Closest_distance(0,n-1)<<endl; return 0; }*/ /*#define MAXLENGTH 1000 #include <stdio.h> #include <string.h> void compute(char * a, char * b,char *c) { int i,j,m,n; long sum,carry; m = strlen(a)-1; n = strlen(b)-1; for(i=m;i>=0;i--) a[i] -= '0'; for(i=n;i >=0;i--) b[i] -='0'; c[m+n+2] ='/0'; carry =0; for(i=m+n;i>=0;i--) { sum=carry; if((j=(i-m))<0) j=0; for(;j<=i&& j <=n;j++) sum += a[i-j]*b[j]; c[i+1] = sum %10 + '0'; /*算?出?保馈?留?的?数簓字?*/ /* carry = sum/10; } if((c[0]=carry+'0')=='0') /* if no carry*/ /* c[0] = '/040'; /* space */ /*} int main() { char a[MAXLENGTH],b[MAXLENGTH],c[MAXLENGTH*2]; puts("输入第一个大整数："); gets(a); puts("输入第二个大整数："); gets(b); compute(a,b,c); puts("结果为:"); for(int i=0;c[i]>=48&&c[i]<=57;i++){ printf("%c",c[i]); } getchar(); } */ #include <stdio.h> #include <stdlib.h> const int N=20; //最多放皇后的个数 int q[N]; //各皇后所在的行号 int cont = 0; //统计解得个数 //输出一个解 void print(int n) { int i,j; cont++; printf("第%d个解：",cont); for(i=1;i<=n;i++) printf("(%d,%d) ",i,q[i]); printf("\n"); } //检验第i行的k列上是否可以摆放皇后 int find(int i,int k) { int j=1; while(j<i) //j=1~i-1是已经放置了皇后的行 { //第j行的皇后是否在k列或(j,q[j])与(i,k)是否在斜线上 if(q[j]==k || abs(j-i)==abs(q[j]-k)) return 0; j++; } return 1; } //放置皇后到棋盘上 void place(int k,int n) { int j; if(k>n) print(n); else { for(j=1;j<=n;j++) //试探第k行的每一个列 { if(find(k,j)) { q[k] = j; place(k+1,n); //递归总是在成功完成了上次的任务的时候才做下一个任务 } } } } int main() { int n; printf("请输入皇后的个数(n<=20),n=:"); scanf("%d",&n); if(n>20) printf("n值太大，不能求解!\n"); else { printf("%d皇后问题求解如下(每列的皇后所在的行数):\n",n); place(1,n); //问题从最初状态解起 printf("\n"); } system("pause"); return 0; }