HDU 1007

テーマの大意はこうです.
座標軸にいくつかの点を与え、これらの点の中で最も近い2つの点間の距離を求める.最終出力の結果は距離の半分です
分析:
これらの点を横座標に従って小さいから大きいまで並べ替え、同じであれば、縦座標に従って小さいから大きいまで並べ替えて、2点間の最小距離len 1を求める.
そして縦座標に従って小さいから大きいまで並べ替えて、同じなら横座標に従って小さいから大きいまで並べ替えて、2点ごとの間の最小の距離len 2を求めます;
最終的な結果はmin(len 1,len 2)である.
  
この問題は作成時に2つの問題に遭遇しました.
1.distance関数、名前の競合が発生し、解決策は自分でdistance参照を再定義する前に::、後者は直接distanceを名前に変更すればいい.
2.バブルソートを使い始めたばかりで、タイムアウトし、O(N*N)、改善方法はalgorithmのsortアルゴリズムを呼び出して、この問題を解決することです.
思考:sortアルゴリズムの時間の複雑さはいくらですか?
ここではsortとクイックソートを比較します.
std::sortで使用されるアルゴリズムは、ほとんどの場合quick sortアルゴリズムよりも速く、quick sortが遅い場合ほど顕著である.Quick sort平均はO(NlogN)であり,最悪の場合はO(N^2)である.std::sortはQuick sortの最悪の状況に対する改善であり、O(Nlogn)の複雑さを維持している.

//
//  main.cpp
//  Demo
//
//  Created by Jaster_chen on 1/27/16.
//  Copyright © 2016 Jaster_chen. All rights reserved.
//

#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
using namespace std;

struct Point
{
    double x;
    double y;
}P[100001];

double distance(Point P1, Point P2)
{
    return sqrt(pow(P1.x-P2.x,2)+pow(P1.y-P2.y,2));
}

bool cmp1(const Point a,const Point b)
{
    if(a.x<b.x)
        return true;
    if(a.x>b.x)
        return false;
    else
        return a.y<b.y;
}

bool cmp2(const Point a,const Point b)
{
    if(a.y<b.y)
        return true;
    if(a.y>b.y)
        return false;
    else
        return a.x<b.x;
}

int main()
{
    double len1,len2;
    int N;
    while(cin>>N&&N!=0)
    {
        for(int i=1;i<=N;i++)
        {
            cin>>P[i].x>>P[i].y;
        }
        sort(P+1,P+N+1,cmp1);
        double min = ::distance(P[1],P[2]);
        double dis;
        for(int i=2;i<N;i++)
        {
            dis = ::distance(P[i],P[i+1]);
            if(dis<min)
                min = dis;
        }
        len1 = min/2.0;
        sort(P+1,P+N+1,cmp2);
        double Min = ::distance(P[1],P[2]);
        double Dis;
        for(int i=2;i<N;i++)
        {
            Dis = ::distance(P[i],P[i+1]);
            if(Dis<Min)
                Min = Dis;
        }
        len2 = Min/2.0;
        if(len1>len2)   len1 = len2;
        cout<<fixed<<setprecision(2)<<len1<<endl;
    }
    return 0;
}

しかし、この問題は後で感覚解法に問題があります.

A(1,100),B(100,1),C(1,1),D(2,2).
①      x          ，  x   ，    y         ，           ，  len1。
       ：C(1,1),A(1,100),D(2,2),B(100,1).
CA    99，AD       （1+98^2）（   98，     98 ），DB      98，    AD DB   98， len1=98。

②      y          ，  y   ，    x         ，           ，  len2。
       ：C(1,1),B(100,1),D(2,2),A(1,100).
CB    99，BD      98，DA     98，    BD DA   98， len2=98.

    ，    ：min（len1，len2），   98。

            CD   ：  2，            ，