如果两个坐标的列是(x1,y1)、(x2,y2)，那么他们之间的距离：SQRT((X1-X2)(X1-X2)+(Y1-Y2)(Y1-Y2)) 

例：



/*
    表名：TpProject   
    FLongitude：经度
    FDimension：纬度
    传入的参数：（121.517759,31.178469）
*/
SELECT * FROM TpProject   
ORDER BY 
SQRT((121.517759-FLongitude)*(121.517759-FLongitude)+(31.178469-FDimension)*(31.178469-FDimension))  

题意：有一群牛，若其中两头牛一起看过一场电影，那么它们的关系是1度的，如果两头牛没有看过同一场电影但它们都与第三头牛是1度的关系，那么他们的关系是2度的。保证没两头牛之间都有关系，求与其他牛之间关系平均度数最小的牛的 平均度数*100，即先找出与其他牛关系度数和的最小。
思路：用floyd（），得到没头牛与其他牛关系度数的最小值。



#include 
#include 
int together[303], degree[303][303];
int n;
void floyd()
{
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
            {
                if(degree[k][i] && degree[k][j])
                {
                    if(degree[i][j] == 0
                       || degree[i][j] > degree[k][i] + degree[k][j])
                    {
                        degree[i][j] = degree[k][i] + degree[k][j];
                    }
                }
            }
}

int main()
{
    #ifdef LOCAL
    freopen("data.in", "r", stdin);
    #endif

    int m, num;
    double sum, ans; // 最后度数之和要除以n-1，要保留小数点后两位
    while(scanf("%d%d", &n, &m) != EOF)
    {
        //printf("n=%d,m=%d\n", n, m);
        memset(degree, 0, sizeof(degree));
        while(m--)
        {
            scanf("%d", &num); //printf("m=%d, num=%d\n", m, n);
            for(int i = 0; i < num; i++)
            {
                scanf("%d", &together[i]);
                for(int j = 0; j < i ; j++)
                {

                    degree[together[i]][together[j]]
                        = degree[together[j]][together[i]] = 1;
                }
            }

        }
        floyd();
        ans = 100000000.0;
        for(int i = 1; i <= n; i++)
        {
            sum = 0;
            for(int j = 1; j <= n; j++)
            {
                if(i != j)
                {
                    sum += degree[i][j] * 1.0;
                }
            }
            if(sum < ans) ans = sum;
        }
        printf("%d\n", (int)(ans / (n - 1) * 100));
    }
    return 0;
}

平面上有n个点P1,P2,…,Pn，n>1,Pi的直角坐标为(Xi,Yi),i=1,2,…,n.求距离最近的两个点及他们之间的距离。
分治法：
将一个大问题缩减到一定的规模变成若干个相同的小问题一一解决。它与动态规划法类似，都是将问题分而治之，变成若干个能够解决小问题，但是动态规划一般分解问题后问题间会互相连续和依赖，而分治法分解后变成一个个独立的问题。
思路
1.在一个平面内的点，先将他们按照x坐标进行排序，将它们以x的中间值的纵轴划分为左右两部分，分别递归找到这两部分中两点之间的最短距离，然后求出左边部分的一个点和右边部分一个点之间最短距离，他们的最小值既是最短距离的两个点。
package algorithm;

import java.util.Arrays;

/**
 * @author Tcc
 */
public class ShortestDistance {

    private double[][] points;

    Point p1, p2;

    public ShortestDistance(double[][] points) {
        this.points = points;
    }

    public double getMinimumDistance() {
        Point[] orderByx = new Point[points.length];
        for (int i = 0; i < orderByx.length; i++){
            orderByx[i] = new Point(points[i][0], points[i][1]);
        }
        //按照x坐标排序
        Arrays.sort(orderByx);
        // 重复点距离为0，不符合题意
        if (checkIdentical(orderByx)) {
            return 0;
        }
        Point[] orderByy = orderByx.clone();
        //按照y坐标排序，方便后续比较距离时简单点
        Arrays.sort(orderByy, new CompareY());
        return distance(orderByx, 0,orderByx.length - 1, orderByy);
    }

    /**
     * 检查重复点
     */
    public boolean checkIdentical(Point[] orderByx) {
        for (int i = 0; i < orderByx.length - 1; i++) {
            if (orderByx[i].compareTo(orderByx[i + 1]) == 0) {
                p1 = orderByx[i];
                p2 = orderByx[i + 1];
                return true;
            }
        }
        return false;
    }

    /**
     * 返回最近的距离
     */
    public double distance( Point[] orderByx, int low, int high,Point[] orderByy) {

        //两个点以下的情况
        if (low >= high){
            return Double.MAX_VALUE;
        } else if (low + 1 == high) {
            p1 = orderByx[low];
            p2 = orderByx[high];
            return distance(orderByx[low], orderByx[high]);
        }

        //把X分为两组，左边和右边
        int mid = (low + high) / 2;
        Point[] orderByyLeft = new Point[mid - low + 1];
        Point[] orderByyRight = new Point[high - mid];
        int j1 = 0;
        int j2 = 0;
        for (int i = 0; i < orderByy.length; i++) {
            if (orderByy[i].compareTo(orderByx[mid]) <= 0){
                orderByyLeft[j1++] = orderByy[i];
            } else{
                orderByyRight[j2++] = orderByy[i];
            }
        }
        //递归找到左边和右边的最近距离值
        double dLeft = distance(orderByx, low, mid, orderByyLeft);
        double dRight = distance(orderByx, mid + 1, high, orderByyRight);
        double d = Math.min(dLeft, dRight);

        // 找到左边离中线距离小于最小距离d的点
        int count = 0;
        for (Point orderByyLeftz : orderByyLeft) {
            if (orderByyLeftz.x >= orderByx[mid].x - d){
                count++;
            }
        }
        Point[] leftPoint = new Point[count];
        count = 0;
        for (Point orderByyLeftz : orderByyLeft) {
            if (orderByyLeftz.x >= orderByx[mid].x - d){
                leftPoint[count++] = orderByyLeftz;
            }
        }

        // 找到右边离中线距离小于最小距离d的点
        count = 0;
        for (Point orderByyRightz : orderByyRight) {
            if (orderByyRightz.x <= orderByx[mid].x + d){
                count++;
            }
        }
        Point[] rightPoint = new Point[count];
        count = 0;
        for (Point orderByyRightz : orderByyRight) {
            if (orderByyRightz.x <= orderByx[mid].x + d){
                rightPoint[count++] = orderByyRightz;
            }
        }

        // 找到这些小于d的点中 左边和右边两边距离最小的值
        double dMid = d;
        int j = 0;
        for (Point aLeftPoint : leftPoint) {
            //过滤一些值
            while (j < rightPoint.length && aLeftPoint.y > rightPoint[j].y + d) {
                j++;
            }
            int k = j;
            while (k < rightPoint.length && rightPoint[k].y <= aLeftPoint.y + d) {
                if (dMid > distance(aLeftPoint, rightPoint[k])) {
                    dMid = distance(aLeftPoint, rightPoint[k]);
                    p1 = aLeftPoint;
                    p2 = rightPoint[k];
                }
                k++;
            }
        }
        return Math.min(d, dMid);
    }

    /**
     * 计算p1和p2的坐标
     */
    public static double distance(Point p1, Point p2) {
       return Math.sqrt(Math.pow(p2.x-p1.x,2)+Math.pow((p2.y-p1.y),2));
    }

    /**
     * 定义一个有x和y坐标点的类
     */
    static class Point implements Comparable<Point> {
        double x;
        double y;
        Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public int compareTo(Point p2) {
            if (this.x < p2.x) {
                return -1;
            } else if (this.x == p2.x) {
                return Double.compare(this.y, p2.y);
            } else {
                return 1;
            }
        }

    }

    /**
     * 先比较y坐标，y坐标相同比较x坐标
     */
    static class CompareY implements java.util.Comparator<Point> {
        @Override
        public int compare(Point p1, Point p2) {
            if (p1.y < p2.y) {
                return -1;
            } else if (p1.y == p2.y) {
                return Double.compare(p1.x, p2.x);
            } else{
                return 1;
            }
        }
    }

    public static void main(String[] args) {

        //随机生成30个点
        double[][] points = new double[30][2];
        for (int i = 0; i < points.length; i++) {
            points[i][0] = Math.random() * 10;
            points[i][1] = Math.random() * 10;
        }
        ShortestDistance shortestDistance = new ShortestDistance(points);
        System.out.println("最短距离：" + shortestDistance.getMinimumDistance());
        System.out.print("(" + shortestDistance.p1.x + ", " + shortestDistance.p1.y + ")和"+"(" + shortestDistance.p2.x + ", " + shortestDistance.p2.y + ")");
        System.out.println();
    }
}

给定两个凸多边形 P 和 Q， 目标是需要找到点对 (p,q) （p 属于 P 且 q 属于 Q） 使得他们之间的距离最大。 


很直观地，这些点不可能属于他们各自多边形的内部。 这个条件事实上与直径问题非常相似： 


两凸多边形 P 和 Q 间最大距离由多边形间的对踵点对确定。 

虽然说法一样， 但是这个定义与给定凸多边形的对踵点对的不同。 

与凸多边形间的对踵点对本质上的区别在于切线是有向且反向的。 下图展示了一个例子： 
 

上述结论暗示不单纯只是顶点对需要检测， 而仅仅是特定的顶点对需要被考虑到。 事实上他们只检测一个基于旋转卡壳模式的算法确立的平行切线。 

考虑如下的算法， 算法的输入是两个分别有 m 和 n 个顺时针给定顶点的凸多边形 P 和 Q。
计算 P 上 y 坐标值最小的顶点（称为 yminP ） 和 Q 上 y 坐标值最大的顶点（称为 ymaxQ）。
为多边形在 yminP 和 ymaxQ 处构造两条切线 LP 和 LQ 使得他们对应的多边形位于他们的右侧。 此时 LP和 LQ 拥有不同的方向， 并且 yminP 和 ymaxQ 成为了多边形间的一个对踵点对。
计算距离(yminP,ymaxQ) 并且将其维护为当前最大值。
顺时针同时旋转平行线直到其中一个与其所在的多边形的边重合。
一个新的对踵点对产生了。 计算新距离， 与当前最大值比较， 如果大于当前最大值则更新。 如果两条线同时与边发生重合， 此时总共三个对踵点对（先前顶点和新顶点的组合）需要考虑在内。
重复执行步骤4和步骤5， 直到新的点对为(yminP,ymaxQ)。
输出最大距离。

旋转卡壳模式确保了所有的对踵点对都被考虑到。 此外， 整个算法拥有线性的时间复杂度， 因为（除了初始化）， 执行步数与顶点数相同。


类似的算法可以被用于凸多边形间最小距离问题中。 


 

原文地址：http://cgm.cs.mcgill.ca/~orm/maxd2p.html