[code=c]
/***********************************************************
* Written by Jowenshaw, 24 Jul 2008.
* Compiled by Turbo C++ 3.0
************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <alloc.h>
#include <math.h>
/////////////////////////////////////////////////////////////////////////////////////
//主要思路：先计算各点到A点的距离，然后按升序排序。
//关键在于排序后离A最近的任意一点都必定位于某个满足要求所取的三点之中。
//其中有一种特例，即所给点有点与A重合的情形，
//这种情形只需在排序后的点列中从近到远取出与A和离A最近的非重合点这两点不共线的第一个点，
//一般情形，通过N截枝法，原因就是按排序后的下标从小到大取点，若某个可能解中的最大下标为N，那么
//可以肯定优于这组解中的点的下标必小于N。本程序便是通过这样逐次缩小选取范围的。
//难点在于判断所选三点组成三角形且包含点A。
/////////////////////////////////////////////////////////////////////////////////////
double MinDistance(int x[], int y[], int n, int x0, int y0, char* id)
{
const double INFITY = 10000000.0; //定义一个充分大的距离上界
int i, j; //循环变量
int ntemp, N; //临时变量,ntemp用于交换，N指可取Q[]中的点列的最大下标
double ftemp; //临时变量,ftemp用于交换
double *dist; //dist[i]存取P[i]点到A的距离
int *ind; //ind[i]为p[i]在按到点A的距离排序后所处的下标
double curMinVal, minVal = INFITY; //对应所选取的三点到点A的距离之和，用于记录当前值和全局最小值
int flag = 0; //flag作为取点是否成功的标志，0表示不成功，1表示成功，也即有无解的标志
strcpy(id, "jowenshaw");
if (n < 3) return 0; //无解的特殊情形
dist = (double *) malloc( n * sizeof (double) );
ind = (int *) malloc( n * sizeof (int) );
//计算P[i]点到A的距离，存与数组dist[], 同时初始化数组ind[]
for (i = 0; i < n; i ++)
{
dist[i] = (x[i] - x0) * (x[i] - x0) + (y[i] - y0) * (y[i] - y0);
ind [i] = i;
}
//用插入排序法对数组dist[]排序
for (i = 1; i < n; i ++)
{
for (j = i; j < n; j ++)
{
if (dist[j] < dist[j-1])
{
ftemp = dist[j-1];
dist[j-1] = dist[j];
dist[j] = ftemp;
ntemp = ind[j-1];
ind[j-1] = ind[j];
ind[j] = ntemp;
}
}//inner for
}//outer for
//记排序后的点列为Q[i], 即令Q[i] = P[ ind[i] ], 其中 i = 0, 1, ..., n-1.
//再分情形讨论：
//（1） Q[0] 和 A 重叠
if (x[ ind[0] ] == x0 && y[ ind[0] ] == y0)
{
for (i = 2; i < n; i ++)
{//判断Q[0], Q[1], Q[i]是否共线，然后处理
if ( (x[ ind[1] ] - x0) * (y[ ind[i] ] - y0) \
!= (y[ ind[1] ] - y0) * (x[ ind[i] ] - x0) )
{
flag = 1;
break;
}
}
minVal = sqrt( dist[1] )+ sqrt( dist[i] );
free(dist);
free(ind);
if (1 == flag) return minVal;
return 0;
}
[/code]
您所在位置：
boxertony [专家分：23030] 发布于 2008-07-17 11:23:00 
