QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#242737#7336. FactoryPetroTarnavskyi#AC ✓26ms3928kbC++171.9kb2023-11-07 16:43:182023-11-07 16:43:21

Judging History

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

  • [2023-11-07 16:43:21]
  • 评测
  • 测评结果:AC
  • 用时:26ms
  • 内存:3928kb
  • [2023-11-07 16:43:18]
  • 提交

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!