【计几】平面最短欧氏距离点对题集

• • • • [SPOJ - Closest Triplet【最小周长三角形】](https://vjudge.ppsucxtt.cn/problem/SPOJ-CLOSEST)
      • [[codeforces] - [School Regional Team Contest, Saratov, 2011]-Minimum Sum【最小向量和】](https://codeforces.com/contest/120/problem/J)
      • [codeforces429D - Tricky Function](https://codeforces.com/contest/429/problem/D)

题意：以给定的 n n n 个点中的3个点组成三角形，求最小周长。

这道题写的挺顺的。

思路：

• 要往最短欧氏距离的方面想。之前的最短点对是最短二元组，这道题是最短三元组。

• 分治，最优解的点要么全在左或全在右，要么左右都有。

• 那么从mid向左右拓展宽度为多少呢？我们知道三元组的周长为d的话，边的最大值为d/2。那么向左或向右拓展宽度为d/2，B点集宽度为d。

• 获得B点集后，对于每个j点，要向上拓展多高呢？同理，也是d/2。我们对于每个j就得到了一个长乘宽=d*(d/2)的矩形，枚举即可。

AC代码：

#include
#include
#include
#include
using namespace std;

const int N=1e6+10;
typedef long long LL;
const double inf = 1e18;


struct point{
    double x, y;
}P[N];
bool cmp_x(point a, point b){
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}
bool cmp_y(int a, int b){
    return P[a].y < P[b].y;
}

double get_dis(int a, int b) { return sqrt((P[a].x - P[b].x) * (P[a].x - P[b].x) + (P[a].y - P[b].y) * (P[a].y - P[b].y)); }


int tmp[N];
int pos;
double closest_pair(int l, int r)
{
    if(l == r - 1) return inf;
    if(l == r - 2) { return get_dis(l, l + 1) + get_dis(l, l + 2) + get_dis(l + 1, l + 2); }

    int mid = l + r >> 1;
    double res = min(closest_pair(l, mid), closest_pair(mid + 1, r));

    pos = 0;
    for(int i=l; i<=r; i++)
        if(fabs(P[i].x - P[mid].x) < res / 2) tmp[pos++] = i;
    sort(tmp, tmp + pos, cmp_y);

    for(int i=0; i 
 
[codeforces] - [School Regional Team Contest, Saratov, 2011]-Minimum Sum【最小向量和】 
题解：Codeforces 120J Minimum Sum
 
Minimum Sum(平面对近点对+分治)
 
思路：向量和 转换成 两点间的距离。把每个点的四种状态都塞到一起，算最近点对。记得要防止一个点的不同状态互相匹配。
 
算距离的话可以用整形存，最后再开方，防止精度问题。懒得改了。
 
AC代码（记得交C++17）：
 
#include
#include
#include
#include
using namespace std;

const int N=4e5+10;
typedef long long LL;
const double inf = 1e9;


struct point{
    int x, y, id, type;
}P[N * 4];
bool cmp_x(const point a, const point b) {
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}
bool cmp_y(const int a, const int b) {
    return P[a].y < P[b].y;
}

double ans = inf;
point ansa, ansb;
void get_dis(int a, int b){
    double dis = sqrt((P[a].x - P[b].x) * (P[a].x - P[b].x) + (P[a].y - P[b].y) * (P[a].y - P[b].y));
    if(dis < ans) ans = dis, ansa = P[a], ansb = P[b];
}


int tmp[N * 4];
int pos;

void closest_pair(int l, int r)
{
    if(l == r) return ;
    if(l == r - 1) { if(P[l].id != P[r].id) get_dis(l, r); return ; }

    int mid = l + r >> 1;
    closest_pair(l, mid); closest_pair(mid + 1, r);

    pos = 0;
    for(int i=l; i<=r; i++)
        if(fabs(P[mid].x * 1.0 - P[i].x) < ans) tmp[pos++] = i;
    sort(tmp, tmp + pos, cmp_y);

    for(int i=0; i 
 
codeforces429D - Tricky Function 
题意：https://vjudge.ppsucxtt.cn/problem/CodeForces-429D#author=yang198866
 
题解：CF429D Tricky Function（求解公式、经分析转为求平面最近点对、思维）
 
思路：
 
两个下标之间的区间和可以转化为前缀和之差，也就是两点距离公式的形式。然后上板子。
 
AC代码：https://codeforces.com/contest/429/submission/128948414