#include <stdio.h>
#include <stdlib.h>
#define N 10
//返回最短距離的平方,兩個點下標分別存在index1和index2中
//x為所有點x坐標數組,y為所有點y坐標數組,n為個數
int getShortest(int *x,int *y,int n,int& index1,int& index2);
int main(int argc, char **argv)
{
int x[10]={11,3,5,7,1,10,17,18,19,20};
int y[10]={0};
int index1,index2;
printf("%d %d %d \n",getShortest(x,y,10,index1,index2),index1,index2);
return 0;
}
/*
* 簡要描述:先找出離第壹個點最近的點,再把第壹個點排除在外,
* 求剩余n-1個點中最近距離,遞推直到剩下兩個點,算法結束
*
*
* */
int getShortest(int *x,int *y,int n,int &minP1,int &minP2)
{
int *px,*py,*currX,*currY;
int minX,minY;
//當前點與第壹個點之間的坐標差值
minX = abs(*(x+1) - *x);
minY = abs(*(y+1) - *y);
//坐標差值絕對值
int absX,absY;
//最短距離平方
long minLen2 ;
long currLen2;
//當前兩點的索引
int *endIndex=x+1;
int *beginIndex=x;
for (px=x,py=y;px<x+n-1;px++,py++)
{
currX = px+1;
currY = py+1;
minLen2 = minX*minX+minY*minY;
while (currX<x+n)
{
absX = abs(*currX-*px);
absY = abs(*currY-*py);
/*比較大小*/
//x,y方向距離都比最小的小,無須計算
if (absX<minX&&absY<minY)
{
minX = absX;
minY = absY;
endIndex = currX;
beginIndex = px;
}
//x,y方向距離壹個大壹個小,計算平方比較
else if ((absX<minX&&absX>minY)||(absX<minX&&absX>minY))
{
currLen2 = (absX*absX+absY*absY);
if (minLen2>currLen2)
{
minLen2 = currLen2;
minX = absX;
minY = absY;
endIndex = currX;
beginIndex = px;
}
}
currX++;
currY++;
}
}
minP1 = beginIndex - x;
minP2 = endIndex - x;
return minLen2;
}