SRM 662 Div2 Hard

TopCoder Statistics - Problem Statement

• 復習。本番通せたとおもったら system test で落とされた。
• 与えられた点が三角形をなし、かつ原点がその三角形含まれるとき、その三角形から脱出するための safe level を計算する必要がある。
• 本番では三角形の内部判定と与えられた点が重複することによって三角形ができないケースが抜けていた。
• unique なものだけ取り除く関数とポリゴン内部判定用の関数をライブラリ化しないとな...。

class Flee {
public:
    vector<int> x;
    vector<int> y;
    double safety(double x0, double y0) {
            double dist = (1<<30);
            REP(i, x.size())
            {
                double d = hypot(x0-x[i], y0-y[i]);
                dist = min(dist, d);
            }
            return dist;
    }
    double cross(double ax, double ay, double bx, double by) {
            return ay*bx-by*ax;
    }
double maximalSafetyLevel(vector <int> _x, vector <int> _y) {
            vector<pair<int,int>> xy;
            REP(i, _x.size())
                xy.emplace_back(_x[i], _y[i]);

            unique(RANGE(xy));
            sort(xy.begin(), xy.end());
            xy.erase(unique(xy.begin(), xy.end()), xy.end());
            REP(i, xy.size())
            {
                x.push_back(xy[i].first);
                y.push_back(xy[i].second);
            }

            double safe = safety(0,0);
            if (x.size()==3)
            {
                bool inside = true;
                REP(i, 3)
                {
                    double vx1 = x[(i+1)%3]-x[i];
                    double vy1 = y[(i+1)%3]-y[i];
                    double vx2 = x[(i+2)%3]-x[i];
                    double vy2 = y[(i+2)%3]-y[i];
                    double ox = -x[i];
                    double oy = -y[i];
                    if (cross(vx1,vy1,ox,oy) * cross(ox,oy,vx2,vy2) < 0)
                        inside = false;
                }
                if (inside)
                {
                    double safe1 = 0;
                    REP(i, 3)
                    {
                        double d  = hypot(x[i]-x[(i+1)%3], y[i]-y[(i+1)%3])*0.5;
                        safe1 = max(safe1, d);
                    }
                    safe = min(safe, safe1);
                }
            }
            return safe;
}
};