QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#143369#6517. Computational GeometryMaxBlazeResFireAC ✓250ms394992kbC++232.5kb2023-08-21 09:25:472023-08-21 09:25:50

Judging History

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

  • [2023-08-21 09:25:50]
  • 评测
  • 测评结果:AC
  • 用时:250ms
  • 内存:394992kb
  • [2023-08-21 09:25:47]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define MAXN 5005
#define INF 4e18

struct vec2{
	int x,y;
	vec2(){}
	vec2( int a , int b ): x(a),y(b){}
	inline vec2 operator +( vec2 B ){ return vec2( x + B.x , y + B.y ); }
	inline vec2 operator -( vec2 B ){ return vec2( x - B.x , y - B.y ); }
}p[MAXN];

inline int Cross( vec2 A , vec2 B ){ return A.x * B.y - A.y * B.x; }

inline int dist( vec2 A , vec2 B ){ return ( A.x - B.x ) * ( A.x - B.x ) + ( A.y - B.y ) * ( A.y - B.y ); }

inline bool online( vec2 A , vec2 B , vec2 C ){ return Cross( A - C , B - C ) == 0; }

int n;
int f[MAXN][MAXN],g[MAXN][MAXN];

inline void solve(){
	scanf("%lld",&n);
	for( int i = 1 ; i <= n ; i ++ ) scanf("%lld%lld",&p[i].x,&p[i].y);
	for( int i = 1 ; i < n ; i ++ ) f[i][i + 1] = dist( p[i] , p[i + 1] );
	for( int len = 3 ; len <= n ; len ++ ){
		for( int l = 1 ; l + len - 1 <= n ; l ++ ){
			int r = l + len - 1;
			//if( online( p[l] , p[( l == n ) ? 1 : l + 1] , p[r] ) || online( p[l] , p[( l == 1 ) ? n : l - 1] , p[r] ) ) f[l][r] = 0;
			f[l][r] = max( max( f[l + 1][r] , f[l][r - 1] ) , dist( p[l] , p[r] ) );
		}
	}
	g[1][n] = dist( p[1] , p[n] );
	for( int len = 3 ; len <= n ; len ++ ){
		for( int l = 1 ; l < len ; l ++ ){
			int r = n - ( len - l ) + 1;
			//if( online( p[l] , p[( l == n ) ? 1 : l + 1] , p[r] ) || online( p[l] , p[( l == 1 ) ? n : l - 1] , p[r] ) ) g[l][r] = 0;
			if( l == 1 ) g[l][r] = max( max( g[l][r + 1] , f[r][n] ) , dist( p[l] , p[r] ) );
			else if( r == n ) g[l][r] = max( max( g[l - 1][r] , f[1][l] ) , dist( p[l] , p[r] ) );
			else g[l][r] = max( max( g[l - 1][r] , g[l][r + 1] ) , dist( p[l] , p[r] ) );
			//cerr << l << " " << r << " " << l << " " << r + 1 << " " << r << " " << n << " " << g[l][r] << "\n";
		}
	}
	// for( int l = 1 ; l <= n - 1 ; l ++ ){
		// for( int r = l + 1 ; r <= n ; r ++ ){
			// cerr << l << " " << r << " " << f[l][r] << " " << g[l][r] << "\n";
		// }
	// }
	int Ans = INF;
	for( int l = 1 ; l <= n - 1 ; l ++ )
		for( int r = l + 1 ; r <= n ; r ++ ){
			if( ( online( p[l] , p[( l == 1 ) ? n : l - 1] , p[r] ) ) || online( p[l] , p[( l == n ) ? 1 : l + 1] , p[r] ) ) continue;
			if( f[l][r] && g[l][r] ) Ans = min( Ans , f[l][r] + g[l][r] );
		}
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j <= n ; j ++ ) f[i][j] = g[i][j] = 0;
	for( int i = 1 ; i <= n ; i ++ ) p[i] = vec2();
	printf("%lld\n",Ans);
}

signed main(){
	int testcase; scanf("%lld",&testcase);
	while( testcase -- ) solve();
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5744kb

input:

2
4
1 0
2 0
1 1
0 0
6
10 4
9 7
5 7
4 5
6 4
9 3

output:

4
44

result:

ok 2 number(s): "4 44"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3936kb

input:

713
8
8 25
3 15
0 5
10 0
19 2
24 6
23 15
15 34
8
25 16
18 25
10 32
1 23
0 14
21 0
27 2
32 6
7
16 15
8 20
1 16
0 12
16 0
21 1
24 5
7
15 1
18 0
24 8
27 15
4 19
0 17
7 8
4
10 20
0 30
15 0
14 10
6
15 0
24 10
21 14
12 14
7 11
0 3
7
18 7
16 9
12 10
6 9
0 4
5 0
15 1
9
0 23
8 13
14 6
24 0
34 1
41 11
37 20
1...

output:

1075
1389
706
687
1550
497
300
1668
471
162
519
190
786
983
367
930
580
524
509
275
617
298
146
1330
494
965
599
1321
866
1210
233
398
560
1548
871
938
366
500
371
1118
1222
1994
712
586
858
624
697
575
1274
882
1035
406
934
670
990
1231
513
2871
939
2735
1610
834
721
585
203
198
1666
617
1166
326
2...

result:

ok 713 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 3976kb

input:

723
6
219724071 0
454078946 131628774
497404433 165947891
427997418 299842932
68283732 510015817
0 327227140
5
277969751 0
576739203 275664810
244855879 638262097
13873538 700473186
0 59956198
10
69526931 509564969
0 395765436
101436487 0
273066511 46581979
904969235 467379058
942000353 535129295
93...

output:

320990950510053393
818929519958899381
1129629590903770087
711353303900820471
683190682500395857
594439231930042527
659610359567672203
1233154227545010165
845514798756141601
410893515758460170
293647337551438590
889581785464512646
1220017957053127490
1180615726625079978
993125871111020743
88416805922...

result:

ok 723 numbers

Test #4:

score: 0
Accepted
time: 4ms
memory: 4844kb

input:

50
100
10788090 640461343
6200823 619327060
0 588075358
2272688 571167135
10484649 531645155
23408105 495027985
37809823 457353729
50543748 426748658
65612394 391936420
74144467 375312692
92238239 342008581
110825102 314274629
136945272 275387892
150625359 258378302
176177538 227408568
211850028 189...

output:

1000855227786024811
909070606999097417
1017431101951290615
990111498358638326
950728988782865680
962774560452779714
996309366656593850
986848706669893356
1081700839718966666
773766023115436171
992970791950402937
973701678270317636
997205411196945405
983632880388713682
992033016531185503
952505046981...

result:

ok 50 numbers

Test #5:

score: 0
Accepted
time: 26ms
memory: 27472kb

input:

5
1000
878526908 228987227
879855378 230541662
883056137 234320630
885582660 237315912
888209996 240551797
891283004 244370572
893274852 246878195
896391978 250849089
898459829 253488754
901495898 257421882
904401963 261232268
906943144 264566136
909037936 267445789
911696142 271101695
913243951 273...

output:

992531084409938036
941345840855103718
1001527316088973221
994659442447419455
991404250855675335

result:

ok 5 number(s): "992531084409938036 94134584085...442447419455 991404250855675335"

Test #6:

score: 0
Accepted
time: 250ms
memory: 394992kb

input:

1
5000
967641745 600438802
967481178 600923111
967219084 601713440
967049837 602223711
966911813 602639084
966682840 603325811
966509662 603840159
966373844 604241989
966137283 604938445
965876558 605705659
965650625 606370144
965512876 606773817
965436585 606996596
965168879 607776452
965094451 607...

output:

977443873239086022

result:

ok 1 number(s): "977443873239086022"

Test #7:

score: 0
Accepted
time: 0ms
memory: 5728kb

input:

3
4
0 0
1000000000 0
1000000000 1000000000
0 1000000000
5
0 0
1 0
1000000000 0
1000000000 1000000000
0 1000000000
6
13 0
51 0
999999989 0
1000000000 999999995
999999995 1000000000
0 999999996

output:

4000000000000000000
3000000000000000001
2999999962000002754

result:

ok 3 number(s): "4000000000000000000 3000000000000000001 2999999962000002754"