这个比赛题目。。。。Orz。。。

kankan

那些参数什么意思
是不是x[]和y[]数目一样啊？
n是什么意思?点数？

晕了太难，按最笨的方法写了一个，但是算法复杂度大，数据一多就不行了。：*

能给出点的数组初始化的值么？
并且告知该范例答案，方便我们测试是否正确啊

太BT了
我今天花了近全天的时间来做

就差一点就好了，实在BT！

越BT越刺激！

这个题目简直就是检测数学功底
更算法都快搭不上边了

产生的随机数很大，题目没规定，这样不好

这多刺激！

//*****************************************************************
// 通过 Dev-C++ 4.9.9.2 测试  *.cpp 
//*****************************************************************
#include <cstdlib>
#include <iostream>
#include <cmath>

using namespace std;
typedef struct 
{
  double dis;     // x与 X0 的距离 
  double deg;     // x与 X0 的夹角 [0 - 2π)
  int index;      // x在原数组的序号 
}PointV;
const int ARRAYLEN = 1000000;
const int X0 = 500, Y0 = 500;
int x[ARRAYLEN],  // = {46, 77, 17},
    y[ARRAYLEN];  // = {64, 23, 38} ;
int n = ARRAYLEN;   
//******************************************************************************
inline void ReRangeAB(double A, double B, double * max1, double * min1, double * max2, double * min2)
{
  *max2 = 0;
  *min2 = 0;
  if ((A <= M_PI) && (B <= M_PI))  //  A,B 都在第一、二象限时 
  {  
    *max1 = (A > B)? (A + M_PI):(B + M_PI);
    *min1 = (A > B)? (B + M_PI):(A + M_PI);
  } 
  else
    if ((A >= M_PI) && (B >= M_PI))  //  A,B 都在第三、四象限时 
    {
      *max1 = (A > B)? (A - M_PI):(B - M_PI);
      *min1 = (A > B)? (B - M_PI):(A - M_PI); 
    }
    else                          //  当 A, B 位于 x 轴的两侧时 
      if(A > B)                   //  当 A 位于三、四象限时 
      {
        *min1 = (B < (A - M_PI))? (A - M_PI):(0);
        *max1 = (B < (A - M_PI))? (B + M_PI):(A - M_PI);
        *min2 = (B < (A - M_PI))? (0):(B + M_PI);
        *max2 = (B < (A - M_PI))? (0):(2 * M_PI);   
      }
      else                        //  A < B ,当 A 位于一二、象限时       
      {
        *min1 = (A < (B - M_PI))? (B - M_PI):(0);
        *max1 = (A < (B - M_PI))? (A + M_PI):(B - M_PI);
        *min2 = (A < (B - M_PI))? (0):(A + M_PI);
        *max2 = (A < (B - M_PI))? (0):(2 * M_PI);  
      } 
}
inline int IsTrig(PointV A, PointV B, PointV C)     // 判断能否组成一个三角形并且含A(x0,y0) 能：返回1 
{
  if  (((A.dis == 0) && (B.dis == 0))        // 当有两个点以上与 (X0,Y0)重合时，肯定不瞒足要求 
    || ((B.dis == 0) && (C.dis == 0)) 
    || ((C.dis == 0) && (A.dis == 0)))
    return 0;
  if (A.dis == 0)      // 当其中一个点与(X0,Y0)重合时，只要另外两个点的角度不相等且不共线时，即满足要求 
    if ((B.deg != C.deg) && (fabs(B.deg - C.deg) != M_PI)) 
      return 1;
    else
      return 0;
  if (B.dis == 0)  
    if ((A.deg != C.deg) && (fabs(A.deg - C.deg) != M_PI))
      return 1;
    else
      return 0;
  if (C.dis == 0)
    if ((B.deg != A.deg) && (fabs(B.deg - A.deg) != M_PI))
      return 1;
    else
      return 0; 
  //************************************************************       
  if ((A.deg == B.deg ) || (B.deg == C.deg) || (A.deg == C.deg)) // 当有两个点的角度相等时，肯定不满足要求 
    return 0;
  if (fabs(A.deg - B.deg) == M_PI)          // 当有两个点共线时，只要第三点不在此线上时即满足要求 
    if ((C.deg != A.deg) && (C.deg != B.deg))
      return 1;
    else
      return 0;
  if (fabs(B.deg - C.deg) == M_PI) 
    if ((A.deg != B.deg) && (A.deg != C.deg))
      return 1;
    else
      return 0;
  if (fabs(A.deg - C.deg) == M_PI) 
    if ((B.deg != A.deg) && (B.deg != C.deg))
      return 1;
    else
      return 0;    
  double maxR1, minR1, maxR2, minR2;            // 一般的点判断 
  ReRangeAB(A.deg, B.deg, &maxR1, &minR1, &maxR2, &minR2);
  if (((C.deg <= maxR1) && (C.deg >= minR1)) ||((C.deg <= maxR2) && (C.deg > minR2))) // 当 C 在 A，B要求的范围时 
    if ((maxR1 != minR1) && ((maxR1 - minR1) != M_PI))  //  且当 C 与 A,B 不共线时 
      return 1;
    else
      return 0;
  else
    return 0;  
}

double MinDistance(int x[], int y[], int n, int x0, int y0, char *id)
{   
  strcpy(id,"tjs125");     // 请在""中填入你的id，主要是方便输出测试结果  
  int i, j, k;
  int tmp, f_canTrig, f_dis_0 =0;
  PointV *pv = new PointV[n];
  double minDis, tmpDis, min1Deg, max1Deg = 0, min2Deg = 2 * M_PI, max2Deg;                    
  for (i = 0; i < n; i++)// 初始化数组 pv,将 x, y 坐标转化为以 X0 为中心极坐标形式 
  {
      pv[i].dis = sqrt(((double)x[i] - x0) * (x[i] - x0) + ((double)y[i] - y0) * (y[i] - y0));
      if((x[i] - x0) != 0)
      {
        if ((x[i] - x0) > 0) 
          if ((y[i] - y0) >= 0)
            pv[i].deg = atan(((double)y[i] - y0) / ((double)x[i] - x0));
          else
            pv[i].deg = 2 * M_PI + atan(((double)y[i] - y0) / ((double)x[i] - x0));
        if ((x[i] - x0) < 0) 
          pv[i].deg = M_PI + atan(((double)y[i] - y0) / ((double)x[i] - x0));
      }
      else
      {
        if ((y[i] - y0) > 0) pv[i].deg = M_PI / 2;
        if ((y[i] - y0) < 0) pv[i].deg = M_PI * 3 / 2;
      }
      pv[i].index = i; 
      if (pv[i].dis == 0)    //以一下部分为当无解时，提供预判断依据 
        if (f_dis_0 != 1)
        {
          f_dis_0 = 1;
          min1Deg = 2 * M_PI;
          max1Deg = 2 * M_PI;
          min2Deg = 2 * M_PI; 
          max2Deg = 2 * M_PI; 
        }       
      if (f_dis_0 == 0)
      {
        if (i == 0)
        {
          min1Deg = pv[i].deg;
          max2Deg = pv[i].deg;
        }
        if (pv[i].deg < min1Deg)
          min1Deg = pv[i].deg;      
        if (pv[i].deg > max2Deg) 
          max2Deg = pv[i].deg;         
        if ((pv[i].deg > M_PI) && (pv[i].deg < min2Deg))
            min2Deg = pv[i].deg; 
        if ((pv[i].deg <= M_PI) && (pv[i].deg > max1Deg))
            max1Deg = pv[i].deg;
      }             
  }
  //printf("%6.5f - %6.5f , %6.5f - %6.5f\n", min1Deg, max1Deg, min2Deg, max2Deg);
  if ((min1Deg != 2 * M_PI) && (max2Deg != 2 * M_PI) && (max2Deg - min1Deg) < M_PI)   // 预判断是否为无解状态 
  {
    //printf(" No Answer, one\n");
    delete []pv;
    return 0;
  }
  if ((max1Deg < M_PI) && (min2Deg > (max1Deg + M_PI))) 
  {
    //printf(" No Answer, two\n");
    delete []pv;
    return 0;
  }
  //对数组 pv 按 dis 值进行希尔排序                                      
  {
    int i, j, gap;
     PointV tmp;
     gap = n / 2;
     while (gap > 0)
     {
        for(i = gap; i < n; i++)
        {
            tmp = pv[i];
            j = i - gap;
            while((j >= 0) && (tmp.dis < pv[j].dis))
            {
                pv[j + gap] = pv[j];
                j = j - gap;
            }      
            pv[j + gap] = tmp;
            j = j - gap;  
        }  
        gap = gap / 2;
     }       
  }
  //printf("running After sort\n");
  minDis = pv[n -1].dis + pv[n - 2].dis + pv[n - 3].dis; 
  f_canTrig = 0;
  double maxR1, minR1, maxR2, minR2;
  for (i = 2; i < n; i++)
  {
    for(j = 0; j < i; j++)      // 求 MinN[i] 值
    {
      for(k = j + 1; k < i; k++)
      {
        tmp = IsTrig(pv[i], pv[j], pv[k]);
        if (tmp == 1)
        {
          f_canTrig = 1;
          tmpDis = pv[i].dis + pv[j].dis + pv[k].dis;
          if (tmpDis < minDis)
            minDis = tmpDis;
          break;
        }  
      }
      if ((j + 2) < i)
        if (minDis < (pv[j + 1].dis + pv[j + 2].dis + pv[i].dis))
          break;
    }    
    if ((i + 1) < n)    // 判断 minDis 是否为最小值
    if (minDis < (pv[i + 1].dis + pv[1].dis + pv[0].dis))
      break;
  }
  if (f_canTrig == 0)         // 无解
    minDis = 0;  
  delete []pv; 
  return minDis;   
}
//******************************************************************************
void InitArrayXY(int x[], int y[], int n)    // 生成1000以内的随机测试数据
{
  int i;
  srand( (unsigned)time(NULL));
  for(i = 0; i < n; i++)
  {
    x[i] = rand() % 1000;
    y[i] = rand() % 1000;
  } 
}
void InitArrayXY(int x[], int y[], int n, int x0, int y0)        // 生成特殊的测试数据
{
  int i;
  srand( (unsigned)time(NULL));
  for(i = 0; i < n; i++)
  {
    x[i] = rand() % 1000 + 2;
    y[i] = rand() % (x[i] - 1);
  } 
}
void PrintXY(int x[], int y[], int n)
{
  printf("x[]={");
  for (int i = 0; i < (n - 1); i++)   
    printf("%4d, ", x[i]);
  printf("%4d}\n", x[n - 1]);  
  printf("y[]={");
  for (int i = 0; i < (n - 1); i++)   
    printf("%4d, ", y[i]);
  printf("%4d}\n", y[n - 1]);  
}
int main(int argc, char *argv[])
{
    char * ipname;
    double minDis;
    clock_t start, finish;
    double duration;
    ipname = (char *)malloc(40 * sizeof(char));   
    InitArrayXY(x, y, n);
    //InitArrayXY(x, y, n, 500, 500);
    //PrintXY(x, y, n);
    start = clock(); 
    minDis = MinDistance(x, y, n, X0 , Y0, ipname); 
    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    printf("Author is : %s\n", ipname);      
    printf("The minimum distance is: %8.4f\n", minDis);
    printf( "time cost: %f seconds\n", duration );
    system("PAUSE");
    return EXIT_SUCCESS;
}