QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#101735 | #3866. Pandemic Restrictions | PetroTarnavskyi# | AC ✓ | 2960ms | 3832kb | C++17 | 2.4kb | 2023-04-30 22:41:30 | 2023-04-30 22:41:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int M = 47;
const double alpha = 0.47;
struct Point {
double x, y;
Point() {}
Point(double _x, double _y): x(_x), y(_y) {}
Point operator+(const Point& p) const {
return {x + p.x, y + p.y};
}
Point operator-(const Point& p) const {
return {x - p.x, y - p.y};
}
Point operator*(double k) const {
return {k * x, k * y};
}
double d2() const {
return x * x + y * y;
}
double len() const {
return sqrt(d2());
}
};
double f(const vector<Point>& p, const Point& q) {
double res = 0;
FOR(i, 0, 3) {
res += (q - p[i]).len();
}
return res;
}
double f(const vector<Point>& p, double x) {
double l = -1e4, r = 1e4;
FOR(i, 0, M) {
double d = (r - l) * alpha, m1 = l + d, m2 = r - d;
if (f(p, Point(x, m1)) < f(p, Point(x, m2))) {
r = m2;
}
else {
l = m1;
}
}
return f(p, Point(x, (l + r) / 2));
}
double f(const vector<Point>& p) {
double l = -1e4, r = 1e4;
FOR(i, 0, M) {
double d = (r - l) * alpha, m1 = l + d, m2 = r - d;
if (f(p, m1) < f(p, m2)) {
r = m2;
}
else {
l = m1;
}
}
return f(p, (l + r) / 2);
}
double g(const vector<Point>& p, const Point& q) {
double res = 0;
FOR(i, 0, 3) {
res = max(res, f(vector<Point>{p[i], p[(i + 1) % 3], q}));
}
return res;
}
double g(const vector<Point>& p, double x) {
double l = -1e4, r = 1e4;
FOR(i, 0, M) {
double d = (r - l) * alpha, m1 = l + d, m2 = r - d;
if (g(p, Point(x, m1)) < g(p, Point(x, m2))) {
r = m2;
}
else {
l = m1;
}
}
return g(p, Point(x, (l + r) / 2));
}
double g(const vector<Point>& p) {
double l = -1e4, r = 1e4;
FOR(i, 0, M) {
double d = (r - l) * alpha, m1 = l + d, m2 = r - d;
if (g(p, m1) < g(p, m2)) {
r = m2;
}
else {
l = m1;
}
}
return g(p, (l + r) / 2);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(10);
vector<Point> p(3);
FOR(i, 0, 3) {
cin >> p[i].x >> p[i].y;
}
cout << g(p) << "\n";
cerr << (double)clock() / CLOCKS_PER_SEC << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2946ms
memory: 3628kb
input:
0 0 5 0 3 3
output:
5.0686139957
result:
ok found '5.06861', expected '5.06861', error '0.00000'
Test #2:
score: 0
Accepted
time: 2960ms
memory: 3704kb
input:
-1 0 0 0 1 0
output:
2.0000000009
result:
ok found '2.00000', expected '2.00000', error '0.00000'
Test #3:
score: 0
Accepted
time: 2939ms
memory: 3708kb
input:
0 0 4000 0 6000 7000
output:
9219.5444572936
result:
ok found '9219.54446', expected '9219.54446', error '0.00000'
Test #4:
score: 0
Accepted
time: 2943ms
memory: 3832kb
input:
-10000 -10000 0 -10000 10000 10000
output:
28284.2712474621
result:
ok found '28284.27125', expected '28284.27125', error '0.00000'
Test #5:
score: 0
Accepted
time: 2932ms
memory: 3704kb
input:
8398 7539 1991 -9953 -1155 6332
output:
18628.4651273261
result:
ok found '18628.46513', expected '18628.46513', error '0.00000'
Test #6:
score: 0
Accepted
time: 2943ms
memory: 3716kb
input:
-10000 10000 0 9999 10000 10000
output:
20000.0000000009
result:
ok found '20000.00000', expected '20000.00000', error '0.00000'
Test #7:
score: 0
Accepted
time: 2935ms
memory: 3700kb
input:
-10000 9987 0 9998 9937 10000
output:
19937.0042383506
result:
ok found '19937.00424', expected '19937.00424', error '0.00000'
Test #8:
score: 0
Accepted
time: 2940ms
memory: 3748kb
input:
10000 10000 9999 10000 10000 9999
output:
1.4142135627
result:
ok found '1.41421', expected '1.41421', error '0.00000'
Test #9:
score: 0
Accepted
time: 2936ms
memory: 3668kb
input:
-10000 -2000 2000 10000 10000 -2000
output:
20274.4559780632
result:
ok found '20274.45598', expected '20274.45598', error '0.00000'
Test #10:
score: 0
Accepted
time: 2941ms
memory: 3700kb
input:
0 0 1 0 1 1
output:
1.4142135625
result:
ok found '1.41421', expected '1.41421', error '0.00000'
Test #11:
score: 0
Accepted
time: 2938ms
memory: 3716kb
input:
1231 244 -1233 3424 0 -11
output:
4022.8964689644
result:
ok found '4022.89647', expected '4022.89647', error '0.00000'
Test #12:
score: 0
Accepted
time: 2936ms
memory: 3816kb
input:
0 0 10000 0 5000 10000
output:
12474.5083578186
result:
ok found '12474.50836', expected '12474.50836', error '0.00000'
Test #13:
score: 0
Accepted
time: 2939ms
memory: 3712kb
input:
0 0 10000 0 5000 1
output:
10000.0000000013
result:
ok found '10000.00000', expected '10000.00000', error '0.00000'
Test #14:
score: 0
Accepted
time: 2939ms
memory: 3712kb
input:
0 0 10000 0 5000 0
output:
10000.0000000013
result:
ok found '10000.00000', expected '10000.00000', error '0.00000'
Test #15:
score: 0
Accepted
time: 2935ms
memory: 3640kb
input:
-10000 -10000 10000 -10000 10000 10000
output:
28284.2712474621
result:
ok found '28284.27125', expected '28284.27125', error '0.00000'
Test #16:
score: 0
Accepted
time: 2941ms
memory: 3632kb
input:
10000 10000 9999 9999 9998 9998
output:
2.8284271251
result:
ok found '2.82843', expected '2.82843', error '0.00000'