ACM模版

描述


题解

最开始想复杂了，画来画去，找不到规律，然后想要用三分来搞，后来发现这其实可以暴力枚举……枚举不同角度即可，题目要求误差不大于 1e−6 1 e − 6 ，但这不是角度的误差范围，我们可以控制角度每次偏移 1e−3 1 e − 3 即可，并不需要也控制在 1e−6 1 e − 6 。具体 1e−6 1 e − 6 会不会超时我也没有尝试……

代码

#include <iostream>
#include <cmath>

using namespace std;

const double ESP = 1e-3;
const double CIR = 360;
const double PI = 3.1415926;

int r;
double x, y, xx, yy;

double dis(double x, double y, double x1, double y1)
{
    return sqrt((x - x1) * (x - x1) + (y - y1) * (y - y1));
}

int main(int argc, const char * argv[])
{
    cin >> r;
    cin >> x >> y;
    cin >> xx >> yy;

    double ans = dis(x, y, xx, yy), x_, y_;
    for (double i = 0; i <= CIR; i += ESP)
    {
        x_ = r * cos((i * PI / 180));
        y_ = r * sin( (i * PI / 180));
        ans = min(ans, dis(x, y, x_, y_) + dis(xx, yy, -x_, -y_));
    }

    printf("%.12lf\n", ans);

    return 0;
}