QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#350954 | #6517. Computational Geometry | User0069 | WA | 1ms | 3700kb | C++14 | 1.4kb | 2024-03-11 10:48:28 | 2024-03-11 10:48:29 |
Judging History
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'