QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#143272#6517. Computational GeometryMaxBlazeResFireWA 2ms7756kbC++232.2kb2023-08-21 00:30:012023-08-21 00:30:02

Judging History

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

  • [2023-08-21 00:30:02]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7756kb
  • [2023-08-21 00:30:01]
  • 提交

answer

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

#define int long long
#define MAXN 5005
#define eps 1e-6
#define INF 3e18

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;
			else 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( ( l == 1 ) && online( p[1] , p[n] , p[r] ) ) g[l][r] = 0;
			else if( ( r == n ) && online( p[1] , p[n] , p[l] ) ) g[l][r] = 0;
			else 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;
			else 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] ) );
			
		}
	}
	int Ans = INF;
	for( int l = 1 ; l <= n - 2 ; l ++ )
		for( int r = l + 2 ; 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;
			Ans = min( Ans , f[l][r] + g[l][r] );
		}
	printf("%lld\n",Ans);
}

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

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 7756kb

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: -100
Wrong Answer
time: 2ms
memory: 5760kb

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:

wrong answer 155th numbers differ - expected: '299', found: '279'