QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#350954#6517. Computational GeometryUser0069WA 1ms3700kbC++141.4kb2024-03-11 10:48:282024-03-11 10:48:29

Judging History

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

  • [2024-03-11 10:48:29]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3700kb
  • [2024-03-11 10:48:28]
  • 提交

answer

#include<bits/stdc++.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=5e3+6;
const int INF=6e18;
const int mod=1e9+7;
int n,f[maxn][maxn];
struct P
{
    int x,y;
}p[maxn];
int d(P x,P y)
{
    return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);
}
int nxt(int i)
{
    return (i+1)%n;
}
void solve()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>p[i].x>>p[i].y;
    }
    for(int i=0;i<n;i++)
    {
        f[i][1]=d(p[i],p[nxt(i)]);
    }
    for(int j=2;j<n;j++)
    {
        for(int i=0;i<n;i++)
        {
            f[i][j]=max({f[i][j-1],f[nxt(i)][j-1],d(p[i],p[(i+j)%n])});
        }
    }
    int ans=INF;
    for(int j=2;j<=n-2;j++)
    {
        for(int i=0;i<n;i++)
        {
            ans=min(ans,f[i][j]+f[(i+j)%n][n-j]);
        }
    }
    cout<<ans<<"\n";
}
signed main()
{
    if (fopen(taskname".INP","r"))
    {
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    Faster
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }

}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3700kb

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: 1ms
memory: 3608kb

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 120th numbers differ - expected: '294', found: '284'