SRM 662 div2 hard:Flee - mayoko’s diary

なんか SRM の div2 hard は難易度に安定感がない感じがする…(こんな簡単じゃないのもたくさんある気がする)

問題

解法

頂点が 2 以下の場合はその 2 頂点がなす直線と直角方向に離れれば 2 頂点との距離が増えていくので safety level は原点で最低になる。
また, 頂点が 3 の場合でも原点がその 3 頂点のなす三角形内部になければ上と同じように適当な方向に逃げることで原点が最低の safety level にすることができる。
残るは 3 頂点の内部に存在する場合。この場合はいずれかの頂点と頂点の間を通らなければならないので, ある頂点とある頂点の中点を通ることになる(それぞれの頂点から半径の等しい円を描いてその外を通って行くことをイメージするとわかりやすそう)。

ということで,

R≤min(max(AB,BC,AC)/2,AO,BO,CO)

となる R が答えですね。

const double INF = 1e9;
double eps = 1e-10;

double add(double a, double b) {
    if (abs(a+b) < eps * (abs(a)+abs(b))) return 0;
    return a+b;
}

bool equal(double a, double b) {
    return add(a, -b) == 0;
}

struct P {
    double x, y;
    P() {}
    P(double x, double y) : x(x), y(y) {}
    P operator+(P p) const {return P(add(x, p.x), add(y, p.y));}
    P operator-(P p) const {return P(add(x, -p.x), add(y, -p.y));}
    P operator*(double d) const {return P(x*d, y*d);}
    double dot(P p) const {return add(x*p.x, y*p.y);} // 内積
    double det(P p) const {return add(x*p.y, -y*p.x);} // 外積
    double dist(P p) const {return sqrt((x-p.x)*(x-p.x) + (y-p.y)*(y-p.y));} // 距離
    void normalize() {double d = sqrt(x*x+y*y); x /= d; y /= d;} // 正規化
    bool operator<(const P& rhs) const {
        if (x != rhs.x) return x < rhs.x;
        return y < rhs.y;
    }
    bool operator==(const P& rhs) const {
        return equal(x, rhs.x) && equal(y, rhs.y);
    }
};

// 点 P が三角形の内部に存在するか
bool inTri(P p, P a, P b, P c) {
    P ab = b-a;
    P bc = c-b;
    P ca = a-c;
    P ap = p-a;
    P bp = p-b;
    P cp = p-c;
    double c1 = ab.det(bp);
    double c2 = bc.det(cp);
    double c3 = ca.det(ap);
    if (c1 > 0 && c2 > 0 && c3 > 0) return true;
    if (c1 < 0 && c2 < 0 && c3 < 0) return true;
    return false;
}

class Flee {
public:
    double maximalSafetyLevel(vector <int> x, vector <int> y) {
        cout << "TEST" << endl;
        int n = x.size();
        double ans = INF;
        for (int i = 0; i < n; i++) {
            ans = min(ans, sqrt(x[i]*x[i] + y[i]*y[i]));
        }
        if (n <= 2) return ans;
        if (!inTri(P(0, 0), P(x[0], y[0]), P(x[1], y[1]), P(x[2], y[2]))) return ans;
        cout << "unko" << endl;
        double tmp = 0;
        for (int i = 0; i < 3; i++) for (int j = i+1; j < 3; j++) {
            int dx = x[j]-x[i];
            int dy = y[j]-y[i];
            double d = sqrt(dx*dx+dy*dy);
            tmp = max(tmp, d/2);
        }
        return min(ans, tmp);
    }
};