QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#101735#3866. Pandemic RestrictionsPetroTarnavskyi#AC ✓2960ms3832kbC++172.4kb2023-04-30 22:41:302023-04-30 22:41:32

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-30 22:41:32]
  • 评测
  • 测评结果:AC
  • 用时:2960ms
  • 内存:3832kb
  • [2023-04-30 22:41:30]
  • 提交

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'