http://acm.hdu.edu.cn/showproblem.php?pid=3548

众所周知,求最近点对有一个(但实际非常快)的暴力剪枝的简单算法。
这题也类似,暴力剪枝。。

(只贴出与题目有关的代码,宏定义见 GitHub

/* 875ms, 268KB */

const double eps = 1e-8;
const int mx = 1e3 + 5;

struct Point
{
    double x, y;
    Point(double x = 0, double y = 0): x(x), y(y) {}
    void read() {SDD(x, y);}
    bool operator < (const Point &b) const
    {
        return x < b.x || x == b.x && y < b.y;
    }
} p[mx];
typedef Point Vec;

Vec operator + (const Vec &a, const Vec &b) {return Vec(a.x + b.x, a.y + b.y);}
Vec operator - (const Point &a, const Point &b) {return Vec(a.x - b.x, a.y - b.y);}
Vec operator - (const Point &a) {return Vec(-a.x, -a.y);}
Vec operator * (const Vec &a, double p) {return Vec(a.x * p, a.y * p);}
Vec operator / (const Vec &a, double p) {return Vec(a.x / p, a.y / p);}

Vec operator * (const Vec &a, const Vec &b) {return Vec(a.x * b.x - a.y * b.y, a.x * b.y + b.x * a.y);}
inline double Dot(const Vec &a, const Vec &b) {return a.x * b.x + a.y * b.y;}
inline double Cross(const Vec &a, const Vec &b) {return a.x * b.y - a.y * b.x;} // b在a左边为正,b在a右边为负,等于0就是平行
inline double Len(const Vec &a) {return hypot(a.x, a.y);}
inline bool isCollinear(const Point &p1, const Point &p2, const Point &p3) {return fabs(Cross(p2 - p1, p3 - p1)) < eps;}

inline bool cmp(const Point &a, const Point &b)
{
    return a.x < b.x;
}

double minTrianglePerimeter(int n)
{
    double ans = 1e100, a;
    int i, j, k;
    For(i, n - 2) Forr(j, i + 1, n - 1)
    {
        if (ans < 2 * (p[j].x - p[i].x) + eps) break; // p[i]太靠左了,直接换下一个p[i+1]
        a = Len(p[j] - p[i]);
        if (ans < 2 * a + eps) continue; // p[i]-p[j]太长了,换下一个p[j+1]
        if (p[i].x == p[j].x) k = upper_bound(p + j + 1, p + n, p[j], cmp) - p;
        // 对于有很多点横坐标相同的情况,我们可以二分找第三个点,不过此题数据太弱,并没有明显的优化
        else k = j + 1;
        for (; k < n; ++k)
        {
            if (ans < 2 * (p[k].x - p[i].x) + eps) break; // p[k]太靠右了,换下一个p[j+1]再循环
            if (!isCollinear(p[i], p[j], p[k])) Qmin(ans, a + Len(p[k] - p[i]) + Len(p[k] - p[j]));
        }
    }
    return ans;
}

int main()
{
    int n, i;
    double ans;
    TT
    {
        Pcas();
        SI(n);
        For(i, n) p[i].read();
        sort(p, p + n);
        ans = minTrianglePerimeter(n);
        ans == 1e100 ? puts("No Solution") : PD(ans);
    }
    return 0;
}

PS:由于判断共线要做乘法,太耗时,可以预处理出距离后判断是否有两边之和等于第三边来优化,那样可以跑到 100+ ms

Comments

comments powered by Disqus