QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#242737 | #7336. Factory | PetroTarnavskyi# | AC ✓ | 26ms | 3928kb | C++17 | 1.9kb | 2023-11-07 16:43:18 | 2023-11-07 16:43:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
db hipot(db a, db b)
{
return sqrt(a * a + b * b);
}
int n;
vector<PII> v;
const int INF = 1'000'447;
db f(db x, db y)
{
db ans = 0;
for (auto [X, Y] : v)
ans += hipot(X - x, Y - y);
return ans;
}
db fBC(db x)
{
db l = -INF, r = INF;
const db coef = (-1 + sqrt(5)) / 2;
const int M = 100;
db m1 = r - coef * (r - l), fm1 = f(x, m1),
m2 = l + coef * (r - l), fm2 = f(x, m2);
FOR(i, 0, M)
{
if (fm1 < fm2)
{
r = m2;
m2 = m1;
fm2 = fm1;
m1 = r - coef * (r - l);
fm1 = f(x, m1);//
}
else
{
l = m1;
m1 = m2;
fm1 = fm2;
m2 = l + coef * (r - l);
fm2 = f(x, m2);//
}
}
return (l + r) / 2;
}
pair<db, db> fAB()
{
db l = -INF, r = INF;
const db coef = (-1 + sqrt(5)) / 2;
const int M = 100;
db m1 = r - coef * (r - l), fm1 = f(m1, fBC(m1)),
m2 = l + coef * (r - l), fm2 = f(m2, fBC(m2));
FOR(i, 0, M)
{
if (fm1 < fm2)
{
r = m2;
m2 = m1;
fm2 = fm1;
m1 = r - coef * (r - l);
fm1 = f(m1, fBC(m1));//
}
else
{
l = m1;
m1 = m2;
fm1 = fm2;
m2 = l + coef * (r - l);
fm2 = f(m2, fBC(m2));//
}
}
return MP((l + r) / 2, fBC((l + r) / 2));
}
void solve()
{
cin >> n;
v.resize(n);
for (auto& [x, y] : v)
cin >> x >> y;
auto res = fAB();
cout << res.F << ' ' << res.S << "\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
int t;
cin >> t;
while(t--)
{
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3828kb
input:
1 3 -3 0 0 3 3 0
output:
-0.000000008897820 1.732050881006769
result:
ok OK!
Test #2:
score: 0
Accepted
time: 26ms
memory: 3904kb
input:
10 3 -3 0 0 3 3 0 2 -1000000 1000000 -1000000 999999 3 -999999 1000000 -1000000 999999 1000000 -1000000 3 -999999 5 4 999999 999998 -999999 30 -6 15 -3 -21 2 12 1 -2 -27 -22 -3 -3 -11 0 -4 16 30 -24 -28 16 9 11 16 30 -28 -11 8 16 -30 28 23 10 -5 -11 28 10 -11 -2 30 -4 11 -17 -12 0 -5 -3 24 -13 22 -1...
output:
-0.000000008897820 1.732050881006769 -1000000.000000002328306 999999.976027468917891 -999999.211296772118658 999999.211369465803728 -211322.141204055573326 211327.973161397152580 1.937519871062457 1.809542859837728 999905.729366264538839 -999901.241956166224554 23.837236995511269 -9.450901367416279 ...
result:
ok OK!
Test #3:
score: 0
Accepted
time: 26ms
memory: 3928kb
input:
10 3 -3 0 0 3 3 0 2 -1000000 1000000 -1000000 999999 3 -999999 1000000 -1000000 999999 1000000 -1000000 3 -999999 5 4 999999 999998 -999999 30 -22 30 0 -19 -29 -2 -7 -21 8 28 6 -5 -21 13 -28 10 -7 11 -23 -4 -22 -5 -16 -12 -20 -11 7 14 -10 -8 -25 26 4 5 -8 5 30 29 6 12 20 -17 -1 12 -10 -7 -4 4 20 -7 ...
output:
-0.000000008897820 1.732050881006769 -1000000.000000002328306 999999.976027468917891 -999999.211296772118658 999999.211369465803728 -211322.141204055573326 211327.973161397152580 -6.249912010303006 2.472720011655554 999915.812498820247129 -999901.145386511692777 -22.827348042661285 26.21693963549041...
result:
ok OK!
Test #4:
score: 0
Accepted
time: 26ms
memory: 3836kb
input:
10 3 -3 0 0 3 3 0 2 -1000000 1000000 -1000000 999999 3 -999999 1000000 -1000000 999999 1000000 -1000000 3 -999999 5 4 999999 999998 -999999 30 -26 -14 18 -28 16 -4 19 18 -29 -20 -23 -17 -8 -16 -5 -20 -3 21 0 -25 -30 10 16 -11 -14 -14 20 18 -15 18 -24 22 -1 -24 -4 -6 -7 9 -1 -19 -29 25 -23 1 -15 7 17...
output:
-0.000000008897820 1.732050881006769 -1000000.000000002328306 999999.976027468917891 -999999.211296772118658 999999.211369465803728 -211322.141204055573326 211327.973161397152580 -4.104530969976175 -4.799102751199380 999899.266694724559784 -999904.209868476027623 3.725303305325530 18.774074346528977...
result:
ok OK!
Test #5:
score: 0
Accepted
time: 26ms
memory: 3844kb
input:
10 3 -3 0 0 3 3 0 2 -1000000 1000000 -1000000 999999 3 -999999 1000000 -1000000 999999 1000000 -1000000 3 -999999 5 4 999999 999998 -999999 30 20 25 10 -20 -22 18 21 16 -4 -25 16 -19 2 19 6 -26 4 -14 -27 -25 24 -28 -8 -29 2 -10 4 -10 21 -21 -1 10 -11 -6 -18 7 -16 -30 10 24 -10 18 -10 -7 -29 25 -26 -...
output:
-0.000000008897820 1.732050881006769 -1000000.000000002328306 999999.976027468917891 -999999.211296772118658 999999.211369465803728 -211322.141204055573326 211327.973161397152580 -0.204092379135612 -8.398511352140797 999894.563540267990902 -999905.994419273687527 -20.549934061777464 1.44905959988535...
result:
ok OK!
Test #6:
score: 0
Accepted
time: 26ms
memory: 3848kb
input:
10 3 -3 0 0 3 3 0 2 -1000000 1000000 -1000000 999999 3 -999999 1000000 -1000000 999999 1000000 -1000000 3 -999999 5 4 999999 999998 -999999 30 -27 5 10 -25 -9 8 28 -4 -30 -22 -22 27 -19 -24 -2 -7 -20 3 16 -16 17 28 -3 2 27 5 7 -21 28 -27 6 -25 -28 -14 5 -14 -29 18 3 9 19 -20 -30 25 -15 26 -29 0 -30 ...
output:
-0.000000008897820 1.732050881006769 -1000000.000000002328306 999999.976027468917891 -999999.211296772118658 999999.211369465803728 -211322.141204055573326 211327.973161397152580 -5.569709378584447 -1.954926915788135 999902.605858592083678 -999893.229065017076209 4.502039870737185 12.047661112413792...
result:
ok OK!
Test #7:
score: 0
Accepted
time: 26ms
memory: 3904kb
input:
10 3 -3 0 0 3 3 0 2 -1000000 1000000 -1000000 999999 3 -999999 1000000 -1000000 999999 1000000 -1000000 3 -999999 5 4 999999 999998 -999999 30 2 -21 23 -17 -30 27 23 17 -5 24 -23 -4 4 -20 -10 29 13 20 29 -5 -10 -29 1 28 19 -16 -19 5 -16 1 0 -21 -28 -20 -8 -19 -5 -30 29 15 18 3 13 -19 3 -9 29 20 20 -...
output:
-0.000000008897820 1.732050881006769 -1000000.000000002328306 999999.976027468917891 -999999.211296772118658 999999.211369465803728 -211322.141204055573326 211327.973161397152580 3.000000000000286 -8.999999999999833 999885.994931960711256 -999902.963663846720010 4.959603472966273 -1.728618191789946 ...
result:
ok OK!