QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#304831 | #6524. Final Defense Line | ucup-team2894# | TL | 1ms | 3900kb | C++17 | 11.9kb | 2024-01-14 03:56:30 | 2024-01-14 03:56:31 |
Judging History
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 ...