分冶法解决大整数相乘 最近对问题

//date:2020.5.9
#include<bits/stdc++.h>
using namespace std;

const int maxn = 100;
void reverse(char a[])
{
    int len = strlen(a);
    for(int i = 0 ; i < len / 2; i++)
    {
        int temp = a[i];
        a[i] = a[len - i - 1];
        a[len - i -1] = temp;
    }
}
int main()
{
    char a[maxn],b[maxn];
    int t[100] = {0};
    printf("Please enter 2 numbers: ");
    scanf("%s%s",a,b);
    reverse(a);
    reverse(b);
    if(strcmp(a,"0")==0||strcmp(b,"0")==0)
        cout<<"0"<<endl;
    else
    {
        int i,j;
        for(i = 0; i <strlen(b); i++)
        {
            int cnt = 0;
            for(j = 0; j < strlen(a); j++)
            {
                int temp = (b[i] - '0') * (a[j] - '0');//表示结果
                int tt= t[i+j] + temp + cnt;//表示与原来计算出对应级数相加
                t[j+i] = tt % 10;
                cnt = tt / 10;//cnt表示是否有进位
            }
            while(cnt != 0)
            {
                t[j+i] = cnt % 10;
                cnt = cnt / 10;
                j++;//此处j++用于结果输出的时候i+j-2对应
            }
        }
        for(int k = i + j - 2; k >= 0; k--)//j比原来的位数多1
        {
            cout<<t[k];
        }
    }
    return 0;
}

//date:2020.5.9
#include<bits/stdc++.h>
using namespace std;
const double inf = 1e20;
const int maxn = 100005;

struct Point
{
    double x, y;
} point[maxn];

int n, mpt[maxn];

//以x为基准排序
bool cmpxy(const Point& a, const Point& b)
{
    if (a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

bool cmpy(const int& a, const int& b)
{
    return point[a].y < point[b].y;
}

double min(double a, double b)
{
    return a < b ? a : b;
}

double dis(int i, int j)
{
    return sqrt((point[i].x - point[j].x)*(point[i].x - point[j].x) + (point[i].y - point[j].y)*(point[i].y - point[j].y));
}

double Closest_Pair(int left, int right)
{
    double d = inf;
    if (left == right)
        return d;
    if (left + 1 == right)
        return dis(left, right);
    int mid = (left + right) >> 1;
    double d1 = Closest_Pair(left, mid);
    double d2 = Closest_Pair(mid + 1, right);
    d = min(d1, d2);
    int i, j, k = 0;//左右两边的都已经找完了
    //分离出宽度为d的区间，找中间d最小的距离
    for (i = left; i <= right; i++)
    {
        if (fabs(point[mid].x - point[i].x) <= d)
            mpt[k++] = i;
    }
    sort(mpt, mpt + k, cmpy);
    //线性扫描
    for (i = 0; i < k; i++)
    {
        for (j = i + 1; j < k && point[mpt[j]].y - point[mpt[i]].y<d; j++)
        {
            double d3 = dis(mpt[i], mpt[j]);
            if (d > d3)
                d = d3;
        }
    }
    return d;
}

int main()
{
    while (~scanf("%d", &n) && n)
    {
        for (int i = 0; i < n; i++)
            scanf("%lf %lf", &point[i].x, &point[i].y);
        sort(point, point + n, cmpxy);
        printf("%.2lf\n", Closest_Pair(0, n - 1) );
    }
    return 0;
}