题解 P1257 【平面上的最接近点对】

北海若 · 2017-07-02 17:58:31 · 题解

听说这道题高级卡常，我来介绍一下怎么削常数。

O(n^2) 两点间距离公式大家都知道，根号下x的差的平方+y的差的平方

但是去掉根号，距离大小比较依然是正确的，可以削掉常数（求根号挺慢的）

然后register不说了，然后能用int尽量int

然后if(a<b) b=a;改成b=a<b?a:b可以节约时间

省掉sqrt时间缩了一半

'''

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int x[10002];
int y[10002];
int main()
{
    int n;
    cin>>n;
    register int tmpx, tmpy;
    register long long tmpz;
    for (int i=0; i<n; i++)
        scanf("%d%d", &x[i], &y[i]);
    long long mindis2 = 4294967296ll;
    for (int i=0; i<n; i++)
        for (int j=i+1; j<n; j++)
        {
            tmpx = x[i] - x[j];
            tmpy = y[i] - y[j];
            tmpz = (long long)tmpx * tmpx + (long long)tmpy * tmpy;
            mindis2 = mindis2 < tmpz ? mindis2 : tmpz;
        }
    printf("%.4f", sqrt(mindis2));
    //getchar();getchar();
    return 0;
}
'''