QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#110823 | #3866. Pandemic Restrictions | gigabuffoon# | AC ✓ | 479ms | 3764kb | C++20 | 3.4kb | 2023-06-04 02:22:04 | 2023-06-04 02:22:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a),end(a)
#define sz(a) int(size(a))
#define rep(i,a,b) for(int i=(a);i<(b);++i)
using vi = vector<int>;
using ll = long long;
using ld = double;
using pll = pair<ll,ll>;
struct Point{
typedef Point P;
ld x, y;
Point(ld x=0, ld y=0): x(x), y(y) {}
bool operator<(P p) const {
return tie(x, y) < tie(p.x, p.y);
}
P operator+(P p) const { return P(x + p.x, y + p.y); }
P operator-(P p) const { return P(x - p.x, y - p.y); }
P operator*(ld d) const { return P(x * d, y * d); }
P operator/(ld d) const { return P(x / d, y / d); }
ld dist2() const { return x*x + y*y; }
ld dist() const { return sqrtl(dist2()); }
};
using P = Point;
using Tri = array<P, 3>;
const int NUM_ITS = 85;
const int MAX_X = 1e4;
// ld gss(ld a, ld b, ld (*f)(ld)) {
template<class F>
ld gss(ld a, ld b, F& f, bool printCoord=false){
ld r = (sqrt(5) - 1) / 2, eps = 1e-9;
ld x1 = b - r * (b - a), x2 = a + r * (b - a);
ld f1 = f(x1), f2 = f(x2);
// switched to fixed iterations
while(b - a > eps)
// for(int it = 0; it < NUM_ITS; ++it)
if(f1 < f2) {
b = x2;
x2 = x1;
f2 = f1;
x1 = b - r * (b - a);
f1 = f(x1);
} else {
a = x1;
x1 = x2;
f1 = f2;
x2 = a + r * (b - a);
f2 = f(x2);
}
if(printCoord) cout << a << endl;
return f(a);
}
pair<ld, ld> getRange(P& A, P& B, P& C, ld x){
// subproblem to Mag
ld tAC = (x - A.x) / (C.x - A.x);
ld y1 = (A + (C - A) * tAC).y, y2;
if(x <= B.x) {
ld tAB = (x - A.x) / (B.x - A.x);
y2 = (A + (B - A) * tAB).y;
} else {
ld tBC = (x - B.x) / (C.x - B.x);
y2 = (B + (C - B) * tBC).y;
}
if(y1 > y2) swap(y1, y2);
return {y1, y2};
}
void solve(){
Tri initTri;
for(int i = 0; i < 3; ++i){
ld x, y;
cin >> x >> y;
initTri[i] = P(x, y);
}
// takes in triangle, tern searches (x, y), runs getCost(Tri tri, P p)
auto solveTri = [&](Tri& tri, auto& getCost) -> ld {
sort(all(tri));
// tern search x, y
ld lx = tri[0].x, rx = tri[2].x;
auto fOfX = [&](ld x) -> ld {
auto [ly, ry] = getRange(tri[0], tri[1], tri[2], x);
auto fOfY = [&](ld y) -> ld {
P p(x, y);
return getCost(tri, p);
};
return gss(ly, ry, fOfY);
};
return gss(lx, rx, fOfX);
};
auto getSumDistsCost = [&](Tri& tri, P& p) -> ld {
ld out = 0;
for(P q : tri) out += (p - q).dist();
return out;
};
auto getHouseCost = [&](Tri& tri, P& p) -> ld {
ld out = 0;
for(int i = 0; i < 3; ++i){
for(int j = i + 1; j < 3; ++j){
Tri newTri = Tri{tri[i], tri[j], p};
out = max(out, solveTri(newTri, getSumDistsCost));
}
}
return out;
};
ld ans = solveTri(initTri, getHouseCost);
cout << setprecision(12) << fixed << ans << "\n";
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
// int t; cin >> t; while(t--)
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 140ms
memory: 3632kb
input:
0 0 5 0 3 3
output:
5.068613995265
result:
ok found '5.06861', expected '5.06861', error '0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
-1 0 0 0 1 0
output:
2.000000000487
result:
ok found '2.00000', expected '2.00000', error '0.00000'
Test #3:
score: 0
Accepted
time: 342ms
memory: 3612kb
input:
0 0 4000 0 6000 7000
output:
9219.544457293516
result:
ok found '9219.54446', expected '9219.54446', error '0.00000'
Test #4:
score: 0
Accepted
time: 374ms
memory: 3688kb
input:
-10000 -10000 0 -10000 10000 10000
output:
28284.271247462639
result:
ok found '28284.27125', expected '28284.27125', error '0.00000'
Test #5:
score: 0
Accepted
time: 346ms
memory: 3756kb
input:
8398 7539 1991 -9953 -1155 6332
output:
18628.465127327709
result:
ok found '18628.46513', expected '18628.46513', error '0.00000'
Test #6:
score: 0
Accepted
time: 173ms
memory: 3572kb
input:
-10000 10000 0 9999 10000 10000
output:
20000.000000000520
result:
ok found '20000.00000', expected '20000.00000', error '0.00000'
Test #7:
score: 0
Accepted
time: 202ms
memory: 3616kb
input:
-10000 9987 0 9998 9937 10000
output:
19937.004238351168
result:
ok found '19937.00424', expected '19937.00424', error '0.00000'
Test #8:
score: 0
Accepted
time: 99ms
memory: 3568kb
input:
10000 10000 9999 10000 10000 9999
output:
1.414213563230
result:
ok found '1.41421', expected '1.41421', error '0.00000'
Test #9:
score: 0
Accepted
time: 479ms
memory: 3744kb
input:
-10000 -2000 2000 10000 10000 -2000
output:
20274.455978062790
result:
ok found '20274.45598', expected '20274.45598', error '0.00000'
Test #10:
score: 0
Accepted
time: 95ms
memory: 3688kb
input:
0 0 1 0 1 1
output:
1.414213562930
result:
ok found '1.41421', expected '1.41421', error '0.00000'
Test #11:
score: 0
Accepted
time: 300ms
memory: 3664kb
input:
1231 244 -1233 3424 0 -11
output:
4022.896468964343
result:
ok found '4022.89647', expected '4022.89647', error '0.00000'
Test #12:
score: 0
Accepted
time: 417ms
memory: 3612kb
input:
0 0 10000 0 5000 10000
output:
12474.508357809911
result:
ok found '12474.50836', expected '12474.50836', error '0.00000'
Test #13:
score: 0
Accepted
time: 165ms
memory: 3764kb
input:
0 0 10000 0 5000 1
output:
10000.000000000749
result:
ok found '10000.00000', expected '10000.00000', error '0.00000'
Test #14:
score: 0
Accepted
time: 2ms
memory: 3608kb
input:
0 0 10000 0 5000 0
output:
10000.000000000422
result:
ok found '10000.00000', expected '10000.00000', error '0.00000'
Test #15:
score: 0
Accepted
time: 395ms
memory: 3752kb
input:
-10000 -10000 10000 -10000 10000 10000
output:
28284.271247462639
result:
ok found '28284.27125', expected '28284.27125', error '0.00000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
10000 10000 9999 9999 9998 9998
output:
2.828427125436
result:
ok found '2.82843', expected '2.82843', error '0.00000'