QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#304831#6524. Final Defense Lineucup-team2894#TL 1ms3900kbC++1711.9kb2024-01-14 03:56:302024-01-14 03:56:31

Judging History

你现在查看的是最新测评结果

  • [2024-01-14 03:56:31]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3900kb
  • [2024-01-14 03:56:30]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(a) (a).begin(), (a).end()
//#define unique(a) a.resize(unique(a.begin(), a.end()) - a.begin())

using namespace std;

#ifdef ONPC
mt19937 rnd(223);
#else
mt19937 rnd(chrono::high_resolution_clock::now()
            .time_since_epoch().count());
#endif

#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

using ll = long long;
using ld = double;

const int maxn = 1e5 + 100, inf = 1e9 + 100;

using T = ld;
constexpr const T EPS = 1e-9;

bool lt(T a, T b) { return a + EPS < b; }

bool le(T a, T b) { return !lt(b, a); }

bool gt(T a, T b) { return lt(b, a); }

bool ge(T a, T b) { return !lt(a, b); }

bool eq(T a, T b) { return !lt(a, b) && !lt(b, a); }

bool ne(T a, T b) { return lt(a, b) || lt(b, a); }

int sgn(T a) { return lt(a, 0) ? -1 : lt(0, a) ? 1 : 0; }

#define OP(op, U, a, x, y) \
pt operator op (U a) const { return pt(x, y); } \
pt &operator op##= (U a) { return *this = *this op a; }
#define CMP(op, body) \
bool operator op (pt p) const { return body; }

struct pt {
    T x, y;

    constexpr pt(T x = 0, T y = 0) : x(x), y(y) {}

    pt operator+() const { return *this; }

    pt operator-() const { return pt(-x, -y); }

    OP(+, pt, p, x + p.x, y + p.y)

    OP(-, pt, p, x - p.x, y - p.y)

    OP(*, T, a, x * a, y * a)

    OP(/, T, a, x / a, y / a)

    friend pt operator*(T a, pt p) {
        return pt(a * p.x, a * p.y);
    }

    bool operator<(pt p) const {
        return eq(x, p.x) ? lt(y, p.y) : lt(x, p.x);
    }

    CMP(<=, !(p < *this))

    CMP(>, p < *this)

    CMP(>=, !(*this < p))

    CMP(==, !(*this < p) && !(p < *this))

    CMP(!=, *this < p || p < *this)

    OP(*, pt, p, x * p.x - y * p.y, y * p.x + x * p.y)

    OP(/, pt, p, (x * p.x + y * p.y) / (p.x * p.x + p.y * p.y),
       (y * p.x - x * p.y) / (p.x * p.x + p.y * p.y))
};

#undef OP
#undef CMP

istream &operator>>(istream &stream, pt &p) {
    return stream >> p.x >> p.y;
}

pt conj(pt a) { return pt(a.x, -a.y); }

T dot(pt a, pt b) { return a.x * b.x + a.y * b.y; }

T cross(pt a, pt b) { return a.x * b.y - a.y * b.x; }

T norm(pt a) { return dot(a, a); }

T abs(pt a) { return sqrt(norm(a)); }

T arg(pt a) { return atan2(a.y, a.x); }

pt polar(T r, T theta) {
    return r * pt(cos(theta), sin(theta));
}

T distSq(pt a, pt b) { return norm(b - a); }

T dist(pt a, pt b) { return abs(b - a); }

T ang(pt a, pt b) { return arg(b - a); }

T ang(pt a, pt b, pt c) {
    a -= b;
    c -= b;
    return arg(pt(dot(c, a), cross(c, a)));
}

T area2(pt a, pt b, pt c) { return cross(b - a, c - a); }

int ccw(pt a, pt b, pt c) { return sgn(area2(a, b, c)); }

pt rot(pt a, pt p, T theta) {
    return (a - p) * pt(polar(T(1), theta)) + p;
}

pt perp(pt a) { return pt(-a.y, a.x); }

struct Circle {
    pt o;
    T r;

    Circle(T r = 0) : o(0, 0), r(r) {}

    Circle(pt o, T r) : o(o), r(r) {}

    int contains(pt p) const { return sgn(r * r - distSq(o, p)); }

    int contains(Circle c) const {
        T dr = r - c.r;
        return lt(dr, 0) ? -1 : sgn(dr * dr - distSq(o, c.o));
    }

    int disjoint(Circle c) const {
        T sr = r + c.r;
        return sgn(distSq(o, c.o) - sr * sr);
    }

    pt proj(pt p) const { return o + (p - o) * r / dist(o, p); }

    pt inv(pt p) const { return o + (p - o) * r * r / distSq(o, p); }
};

struct Line {
    pt v;
    T c;

// ax + by = c , l e f t side is ax + by > c
    Line(T a = 0, T b = 0, T c = 0) : v(b, -a), c(c) {}

// direction vector v with o f fs e t c
    Line(pt v, T c) : v(v), c(c) {}

// points p and q
    Line(pt p, pt q) : v(q - p), c(cross(v, p)) {}

    T eval(pt p) const { return cross(v, p) - c; }

// sign of onLeft , d is t : 1 i f l e f t of line , 0 i f on line , −1
    int onLeft(pt p) const { return sgn(eval(p)); }

    T dist(pt p) const { return eval(p) / abs(v); }

    T distSq(pt p) const {
        T e = eval(p);
        return e * e / norm(v);
    }

    Line perpThrough(pt p) const { return Line(p, p + perp(v)); }

    Line translate(pt p) const { return Line(v, c + cross(v, p)); }

    Line shiftLeft(T d) const { return Line(v, c + d * abs(v)); }

    pt proj(pt p) const { return p - perp(v) * eval(p) / norm(v); }

    pt refl(pt p) const {
        return p - perp(v) * T(2) * eval(p) / norm(v);
    }

    int cmpProj(pt p, pt q) const {
        return sgn(dot(v, p) - dot(v, q));
    }
};

Line bisector(Line l1, Line l2, bool interior) {
    T s = interior ? 1 : -1;
    return Line(l2.v / abs(l2.v) + l1.v / abs(l1.v) * s,
                l2.c / abs(l2.v) + l1.c / abs(l1.v) * s);
}

int lineLineIntersection(Line l1, Line l2, pt &res) {
    T d = cross(l1.v, l2.v);
    if (eq(d, 0)) return l2.v * l1.c == l1.v * l2.c ? 2 : 0;
    res = (l2.v * l1.c - l1.v * l2.c) / d;
    return 1;
}

bool onSeg(pt p, pt a, pt b) {
    return !ccw(p, a, b) && !lt(0, dot(a - p, b - p));
}

int segSegIntersects(pt a, pt b, pt p, pt q) {
    if (ccw(a, b, p) * ccw(a, b, q) < 0
        && ccw(p, q, a) * ccw(p, q, b) < 0)
        return 1;
    if (onSeg(p, a, b) || onSeg(q, a, b)
        || onSeg(a, p, q) || onSeg(b, p, q))
        return 2;
    return 0;
}

vector<pt> segSegIntersection(pt a, pt b, pt p, pt q) {
    int intersects = segSegIntersects(a, b, p, q);
    if (!intersects) return vector<pt>();
    if (intersects == 1) {
        T c1 = cross(p - a, b - a), c2 = cross(q - a, b - a);
        return vector<pt>{(c1 * q - c2 * p) / (c1 - c2)};
    }
    vector<pt> ret;
    if (onSeg(p, a, b)) ret.push_back(p);
    if (onSeg(q, a, b)) ret.push_back(q);
    if (onSeg(a, p, q)) ret.push_back(a);
    if (onSeg(b, p, q)) ret.push_back(b);
    sort(ret.begin(), ret.end());
    ret.erase(unique(ret.begin(), ret.end()), ret.end());
    return ret;
}

pt closestPtOnSeg(pt p, pt a, pt b) {
    if (a == b) return a;
    T d = distSq(a, b), t = min(d, max(T(0), dot(p - a, b - a)));
    return a + (b - a) * t / d;
}

T ptSegDist(pt p, pt a, pt b) {
    if (a == b) return dist(a, p);
    T d = distSq(a, b), t = min(d, max(T(0), dot(p - a, b - a)));
    return abs((p - a) * d - (b - a) * t) / d;
}

T segSegDist(pt a, pt b, pt p, pt q) {
    return segSegIntersects(a, b, p, q) > 0
           ? 0
           : min({ptSegDist(p, a, b), ptSegDist(q, a, b),
                  ptSegDist(a, p, q), ptSegDist(b, p, q)});
}

vector<pt> circleLineIntersection(Circle c, Line l) {
    vector<pt> ret;
    T h2 = c.r * c.r - l.distSq(c.o);
    pt p = l.proj(c.o);
    if (eq(h2, 0)) ret.push_back(p);
    else if (lt(0, h2)) {
        pt h = l.v * sqrt(h2) / abs(l.v);
        ret.push_back(p - h);
        ret.push_back(p + h);
    }
    return ret;
}

vector<pt> circleSegIntersection(Circle c, pt a, pt b) {
    vector<pt> ret;
    if (a == b) { if (c.contains(a) == 0) ret.push_back(a); }
    else {
        Line l(a, b);
        for (auto &&p: circleLineIntersection(c, l))
            if (l.cmpProj(a, p) <= 0 && l.cmpProj(p, b) <= 0)
                ret.push_back(p);
    }
    return ret;
}

T circleHalfPlaneIntersectionArea(Circle c, Line l) {
    T h2 = c.r * c.r - l.distSq(c.o), ret = 0;
    if (!lt(h2, 0)) {
        pt p = l.proj(c.o), h = l.v * sqrt(max(h2, T(0))) / abs(l.v);
        pt a = p - h, b = p + h;
        T theta = abs(ang(a, c.o, b));
        ret = c.r * c.r * (theta - sin(theta)) / 2;
    }
    if (l.onLeft(c.o) > 0) ret = acos(T(-1)) * c.r * c.r - ret;
    return ret;
}

bool fail_circle;

// f i r s t point is guaranteed to not be on the l e f t side of
// l ine from c1 .o to c2 .o
pt circleCircleIntersection(Circle c1, Circle c2, int ts) {
    fail_circle = 0;
    pt d = c2.o - c1.o;
    T d2 = norm(d);
    if (eq(d2, 0)) return eq(c1.r, c2.r) ? 2 : 0;
    T pd = (d2 + c1.r * c1.r - c2.r * c2.r) / 2;
    T h2 = c1.r * c1.r - pd * pd / d2;
    pt p = c1.o + d * pd / d2;
    if (eq(h2, 0)) return p;
    else if (lt(0, h2)) {
        pt h = perp(d) * sqrt(h2 / d2);
        if (ts == 0)
            return p - h;
        else
            return p + h;
    } else {
        fail_circle = 1;
        return {0, 0};
    }
}

const int CS = 35;

const ld eps = 1e-6;

template<typename F>
ld get_min(ld l, ld r, F f) {
    if (abs(r - l) < eps)
        return (l + r) / 2;
    for (int it = 0; it < CS; it++) {
        ld m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
        if (f(m1) < f(m2))
            r = m2;
        else
            l = m1;
    }
    return (l + r) / 2;
}

template<typename F>
ld get_zero(ld l, ld r, F f) {
    if (abs(r - l) < eps)
        return (l + r) / 2;
    bool inc = (f(l) < f(r));
    for (int it = 0; it < CS; it++) {
        ld m = (l + r) / 2;
        if (inc ^ (f(m) >= 0))
            l = m;
        else
            r = m;
    }
    return (l + r) / 2;
}

void solve() {
    vector<int> d(3);
    vector<pt> p(3);
    for (int i = 0; i < 3; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        p[i].x = a;
        p[i].y = b;
        d[i] = c;
    }
    vector<pt> cands;
    ld og[3][3];
    for (int i = 0; i < 3; i++)
        for (int j = i + 1; j < 3; j++) {
            // r - d1 >= 0, r >= d1, r - d2 = ds
            ld r = max({(ld)d[i], (ld)d[j], (ld)(dist(p[i], p[j]) + d[i] + d[j]) / 2});
            og[i][j] = r;
            for (int ts = 0; ts < 2; ts++) {
                auto w = circleCircleIntersection({p[i], r - d[i]}, {p[j], r - d[j]}, ts);
                if (!fail_circle)
                    cands.push_back(w);
            }
        }
    bool fail = 0;
    for (int ts = 0; ts < 2; ts++) {
        auto f = [&](ld r) {
            auto z = circleCircleIntersection({p[0], r - d[0]}, {p[1], r - d[1]}, ts);
            if (fail_circle) {
                fail = 1;
                return (ld)0;
            }
            return r - d[2] - dist(z, p[2]);
        };
        auto fp = [&](ld r) {
            auto z = circleCircleIntersection({p[0], r - d[0]}, {p[1], r - d[1]}, ts);
            if (fail_circle) {
                return pt{0, 0};
            }
            return z;
        };
        auto f1 = [&](ld r) {
            return -f(r);
        };
        ld l = og[0][1], r = 1e4;
        ld m1 = get_min(l, r, f);
        if (fail) {
            cout << "0\n";
            return;
        }
        ld m2 = get_min(l, r, f1);
        if (m1 > m2)
            swap(m1, m2);
        for (auto [x, y] : vector<pair<ld, ld>>{{l, m1}, {m1, m2}, {m2, r}})
            cands.push_back(fp(get_zero(x, y, f)));
    }
    auto eq = [&](ld x, ld y) {
        return abs(x - y) < eps;
    };
    // filter cands
    {
        vector<pt> os;
        for (auto i : cands) {
            bool has = 0;
            for (auto w : os)
                if (eq(dist(i, w), 0))
                    has = 1;
            if (!has)
                os.push_back(i);
        }
    }
    // then check
    ld best = 1e18;
    int cs = 0;
    for (auto c : cands) {
        ld r = dist(c, p[0]) + d[0];
        bool match = 1;
        for (int i = 1; i < 3; i++)
            if (eq(r - d[i], dist(p[i], c)));
            else
                match = 0;
        if (match) {
//            cerr << "has " << r << '\n';
            cs++;
            if (best > r) {
                best = r;
            }
        }
    }
    if (cs > 4)
        cout << "-1\n";
    else if (cs == 0)
        cout << cs << '\n';
    else
        cout << cs << ' ' << best << '\n';
}

int main() {
#ifdef ONPC
    freopen("../a.in", "r", stdin);
//    freopen("../a.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;
    cout.precision(10);
    int ts;
    ts = 2e5;
    cin >> ts;
    while (ts--)
        solve();
    cerr << "\n\nConsumed " << TIME << endl;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3900kb

input:

2
0 0 1
3 0 2
10 2 2
0 0 1
3 0 2
10 2 -2

output:

2 10.3273292117
2 5.3417308377

result:

ok 2 cases

Test #2:

score: -100
Time Limit Exceeded

input:

200000
10 0 30
0 0 20
-50 0 2
10 0 30
0 0 20
-50 0 -2
10 0 30
0 0 20
-50 1 2
10 0 30
0 0 20
-50 1 -2
10 0 30
0 0 20
-50 2 2
10 0 30
0 0 20
-50 2 -2
10 0 30
0 0 20
-50 3 2
10 0 30
0 0 20
-50 3 -2
10 0 30
0 0 20
-50 4 2
10 0 30
0 0 20
-50 4 -2
10 0 30
0 0 20
-50 5 2
10 0 30
0 0 20
-50 5 -2
10 0 30
0 0...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result: