QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#188911 | #4886. Best Sun | Dualqwq | AC ✓ | 1745ms | 9196kb | C++23 | 7.0kb | 2023-09-26 16:33:08 | 2023-09-26 16:33:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 3e2 + 5;
typedef long long i64;
typedef double db;
typedef pair<int,int> pii;
#define FI first
#define SE second
const db eps = 1e-9,PI = acos(-1.0);
mt19937 Rnd(1919810);
struct Vec {
int x,y;
Vec(){}
Vec(const int _x,const int _y):x(_x),y(_y){}
inline Vec operator + (const Vec &rhs) const { return Vec(x + rhs.x,y + rhs.y);}
inline Vec operator - (const Vec &rhs) const { return Vec(x - rhs.x,y - rhs.y);}
inline i64 operator * (const Vec &rhs) const { return 1ll * x * rhs.y - 1ll * y * rhs.x;}
inline bool operator == (const Vec &rhs) const { return x == rhs.x && y == rhs.y;}
};
Vec O(0,0);
inline bool Cmp(const Vec &x,const Vec &y) { return (x.y == y.y) ? (x.x < y.x) : (x.y < y.y);}
inline i64 Dot(const Vec &A,const Vec &B) { return 1ll * A.x * B.x + 1ll * A.y * B.y;}
inline db Distance(const Vec &A,const Vec &B) { return sqrt(Dot(A - B,A - B));}
inline db Area(const Vec &A,const Vec &B,const Vec &C) { return 0.5 * abs(A * B + B * C + C * A);}
inline bool Equal(const db &A,const db &B) { return fabs(A - B) < eps;}
inline bool InSegment(const Vec &A,const Vec &B,const Vec &p) { return Equal(Distance(A,p) + Distance(p,B),Distance(A,B));}
inline bool InTriangle(const Vec &A,const Vec &B,const Vec &C,const Vec &p) {
if((B - A) * (p - A) >= 0 && (C - B) * (p - B) >= 0 && (A - C) * (p - C) >= 0) return true;
if((B - A) * (p - A) <= 0 && (C - B) * (p - B) <= 0 && (A - C) * (p - C) <= 0) return true;
return false;
// return Area(A,B,p) + Area(B,C,p) + Area(C,A,p) == Area(A,B,C);
}
inline Vec Rotate(const Vec &A) { return Vec(-A.y,A.x);}
inline int sgn(const Vec &A) { return A.y > 0 || A.y == 0 && A.x > 0;}
Vec p[N];
int n;
int V[N][N],VL[N][N];
int TagO;
db sum[N][N];
inline int NeedAdd(const Vec &A,const Vec &B,const Vec &p) {
if(!InTriangle(O,A,B,p)) return 0;
if(!p.x && !p.y) return 0;
// if(InSegment(A,B,p)) return 0;
if((O - p) * (A - p) == 0
|| (O - p) * (B - p) == 0 || (A - p) * (B - p) == 0) return 1;
return 2;
}
inline bool CheckTriangle(int i,int j,int k) {
if(InSegment(p[i],p[j],p[k])) return VL[i][j] <= 1;
if(InSegment(p[i],p[k],p[j])) return VL[i][k] <= 1;
if(InSegment(p[j],p[k],p[i])) return VL[j][k] <= 1;
int tmp = TagO - (p[i] == O) - (p[j] == O) - (p[k] == O);
if(tmp && InTriangle(p[i],p[j],p[k],O)) return false;
if(VL[i][j] || VL[j][k] || VL[i][k]) return false;
// if(i == 1 && j == 1 && k == 4) puts("done");
int num = 0;
int v1 = V[i][j] - NeedAdd(p[i],p[j],p[k]);
int v2 = V[j][k] - NeedAdd(p[j],p[k],p[i]);
int v3 = V[k][i] - NeedAdd(p[k],p[i],p[j]);
if(p[i] * p[j] > 0) num += v1; else if(p[i] * p[j] < 0) num -= v1;
if(p[j] * p[k] > 0) num += v2; else if(p[j] * p[k] < 0) num -= v2;
if(p[k] * p[i] > 0) num += v3; else if(p[k] * p[i] < 0) num -= v3;
// 上面没有计算 Op[i],Op[j],Op[k] 三条线的结果
// int brt = 0;
// for(int t = 1;t <= n;t++)
// if(i != t && j != t && k != t && InTriangle(p[i],p[j],p[k],p[t])) ++brt;
// if((abs(num) > 0) ^ (brt > 0)) {
// printf("%d %d %d\n",i,j,k);
// printf("p[%d]:%d,%d\n",1,p[1].x,p[1].y);
// printf("p[%d]:%d,%d\n",2,p[2].x,p[2].y);
// printf("p[%d]:%d,%d\n",3,p[3].x,p[3].y);
// printf("p[%d]:%d,%d\n",4,p[4].x,p[4].y);
// printf("%d %d %d\n",v1,v2,v3);
// exit(2145);
// }
// assert(num % 2 == 0);
// assert(abs(num) == brt);
return num == 0;
}
struct Line {
int s,t,type;
Vec v;
Line(){}
Line(const int _s,const int _t,const int _type,const Vec _v):
s(_s),t(_t),type(_type),v(_v){}
inline bool operator < (const Line &rhs) const {
// return Angle(v) < Angle(rhs.v);
int t1 = sgn(this->v),t2 = sgn(rhs.v);
if(t1 != t2) return t1 > t2;
i64 val = this->v * rhs.v;
// db val = Angle(this->v) - Angle(rhs.v);
if(val) return val > 0;
else return type < rhs.type;
}
};
Line L[N * N * 2];
int tot;
inline void Init() {
cin >> n;
for(int i = 1;i <= n;i++) cin >> p[i].x >> p[i].y;
TagO = 0;
for(int i = 1;i <= n;i++) if(p[i] == O) TagO++;
sort(p + 1,p + n + 1,Cmp);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
if(i < j)
for(int k = 1;k <= n;k++) {
if(k == i || k == j) continue;
if(p[k] == O) continue;
if(!InTriangle(p[i],O,p[j],p[k])) continue;
// if(InSegment(O,p[i],p[k]) || (!InSegment(O,p[j],p[k]) && !InSegment(O,p[i],p[k])))
// // if(InSegment(p[i],p[j],p[k]) || (!InSegment(O,p[i],p[k]) && !InSegment(O,p[j],p[k])))
V[i][j] += NeedAdd(p[i],p[j],p[k]);
if(InSegment(p[i],p[j],p[k])) ++VL[i][j];
}
else V[i][j] = V[j][i],VL[i][j] = VL[j][i];
// printf("V,VL[1,2]:%d,%d\n",V[1][2],VL[1][2]);
// printf("V,VL[3,1]:%d,%d\n",V[3][1],VL[3][1]);
// printf("V,VL[2,3]:%d,%d\n",V[2][3],VL[2][3]);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
for(int k = 1;k <= n;k++) {
if(k == i || k == j) continue;
if((p[k] - p[i]) * (p[j] - p[i]) <= 0) continue;
if(Dot(p[j] - p[i],p[k] - p[i]) >= 0 && Dot(p[i] - p[j],p[k] - p[j]) > 0)
sum[i][j] += min(Distance(p[k],p[i]),Distance(p[k],p[j]));
}
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++) {
if(i == j) continue;
sum[i][j] += Distance(p[i],p[j]);
L[++tot] = Line(i,j,0,p[j] - p[i]);
L[++tot] = Line(i,j,1,Rotate(p[j] - p[i]));
}
// printf("Angle(1,2):%.6lf\n",Angle(p[2] - p[1]));
// printf("Angle(1,3):%.6lf\n",Angle(p[3] - p[1]));
// printf("Angle(2,1):%.6lf\n",Angle(p[1] - p[2]));
// printf("Angle(2,3):%.6lf\n",Angle(p[3] - p[2]));
// printf("Angle(3,1):%.6lf\n",Angle(p[1] - p[3]));
// printf("Angle(3,2):%.6lf\n",Angle(p[2] - p[3]));
sort(L + 1,L + tot + 1);
cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
}
db dp[N];
inline bool Check(int st,db mid) {
for(int i = 1;i <= n;i++) dp[i] = -1e15;
dp[st] = -eps;
// printf("Check:%d\n",st);
for(int i = 1;i <= tot;i++) {
int s = L[i].s,t = L[i].t,tp = L[i].type;
// printf("L:%d,%d,%d\n",s,t,tp);
// printf("CheckTriangle[%d,%d,%d]:%d\n",st,s,t,CheckTriangle(st,s,t));
if(tp == 1) {
if(s >= st) dp[s] -= mid * Distance(p[s],p[t]);
} else
if(s >= st && t >= st && CheckTriangle(st,s,t))
dp[t] = max(dp[t],dp[s] + Area(p[st],p[s],p[t]) - mid * sum[s][t]);
}
// for(int i = 1;i <= n;i++) printf("dp[%d]=%.12lf\n",i,dp[i]);
return dp[st] > eps;
}
inline void Clr(int n) {
for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) V[i][j] = VL[i][j] = sum[i][j] = 0;
tot = 0;
}
inline void work() {
Clr(n);
Init();
static int perm[N];
for(int i = 1;i <= n;i++) perm[i] = i;
shuffle(perm + 1,perm + n + 1,Rnd);
db ans = 0;
// printf("Check:%d\n",Check(1,0));
for(int i = 1;i <= n;i++)
if(Check(perm[i],ans)) {
db lef = ans,rig = 1e6;
for(int _ = 1;_ <= 45;_++) {
db mid = (lef + rig) / 2;
if(Check(perm[i],mid)) lef = mid;
else rig = mid;
}
ans = lef;
}
printf("%.10lf\n",ans);
cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
}
int main() {
int T;
cin >> T;
while(T--) work();
return 0;
}
/*
1
4
1 -4
3 -3
1 -1
2 1
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4116kb
input:
4 3 -1 -1 1 -1 0 1 4 0 0 10 0 0 10 8 1 5 2 0 -2 0 1 1 -1 1 0 3 8 4 4 -4 4 4 -4 -4 -4 5 6 -6 5 -5 -6 6 -5
output:
0.3090169685 1.2368613993 0.2711375252 1.5631001995
result:
ok 4 numbers
Test #2:
score: 0
Accepted
time: 80ms
memory: 4040kb
input:
10000 3 702262 828158 -350821 -420883 -466450 13507 3 28647 -193498 126436 -864937 -287798 738936 3 270358 -269567 745815 -485408 834083 677952 3 -2036 -403634 742978 -263774 975937 -609237 3 584248 -472620 482016 -356760 284902 903881 3 -292004 504925 -935756 373793 -781101 -434659 3 -858513 684433...
output:
85789.0873983536 18268.5193616692 102489.9883902606 66685.7544280788 18674.6579373960 106468.9651319668 14427.0246510700 29966.2453025178 143547.7510835596 13097.1756881024 162410.1683169670 72070.9324178586 29369.9926278634 52867.2944310813 90314.3083467341 99775.9271965606 144449.7053083467 64406....
result:
ok 10000 numbers
Test #3:
score: 0
Accepted
time: 98ms
memory: 6056kb
input:
10000 3 2 2 2 -2 -5 -5 3 -3 5 5 -4 2 -2 3 -4 1 2 -2 -4 4 3 1 -4 2 1 -4 1 3 2 1 -1 1 -3 3 3 4 5 3 -1 -3 -3 3 1 5 5 0 5 -1 3 2 -3 -5 -3 5 3 3 -4 4 0 -5 5 4 3 2 -3 5 0 2 -5 3 -2 -3 5 -3 5 4 3 -1 4 4 4 4 3 3 5 3 -1 4 2 -1 3 2 -3 4 3 -4 3 3 0 4 -2 -2 -1 -3 3 -2 0 -4 -2 4 2 3 -3 -1 3 1 1 -3 3 2 -5 2 3 -4 ...
output:
0.6507006844 0.2268090498 0.4946825527 0.8255326236 0.2675324708 0.7379284455 0.1368529183 0.8277457937 1.3896280961 0.2484761410 1.0251262381 0.2252451168 0.7981688270 1.0521776233 0.2700907373 0.2210279888 0.6549291243 1.0657925316 0.1207361606 0.1727212009 0.4458825060 0.2484761410 0.1224985624 0...
result:
ok 10000 numbers
Test #4:
score: 0
Accepted
time: 108ms
memory: 4036kb
input:
5625 4 -405394 -381883 602267 -335687 -620806 984110 271283 531233 4 196903 -993060 290851 358123 -890076 -717709 -681138 209884 4 -849589 607722 -21517 -586295 208561 -220953 924518 622983 4 -832186 456270 289934 43656 636006 339718 188963 113907 4 -305762 -872205 -520125 368722 -774548 984204 4245...
output:
232625.0042744107 268175.8269859619 159589.3236305130 60440.7530425703 133893.1234363469 63201.9907486067 167697.6634061235 129470.0132843047 126903.8540727934 106643.9712630825 131692.3112278801 100421.0550161986 148490.2748178740 68842.2423098165 241376.1911161032 303904.5464356604 77462.333614761...
result:
ok 5625 numbers
Test #5:
score: 0
Accepted
time: 133ms
memory: 6044kb
input:
5625 4 -2 -1 4 -5 -2 -4 -4 -4 4 -1 -5 4 4 2 -5 -5 1 4 -3 -4 -3 -1 -5 -1 4 -2 4 -2 4 -4 1 -1 -1 5 -4 4 -3 -5 -1 4 5 -1 3 5 4 -4 -2 1 4 -1 1 3 4 4 -5 3 -3 3 5 -4 -1 4 4 1 2 2 -5 1 0 0 -3 4 -5 -4 2 -3 5 3 -3 2 4 2 -2 -4 3 1 -4 -5 -5 4 -3 5 -2 4 1 3 1 -4 4 0 -5 5 -5 0 -2 -3 2 4 0 5 -1 -4 -2 0 4 -1 4 4 -...
output:
0.4919681942 1.6080239257 0.6764635424 0.8146821049 1.5727954005 0.2020447880 0.4423672879 0.3055831996 1.5089069052 1.3227875115 0.5218559238 0.3982804238 1.2194946066 1.1774912423 1.3951026858 1.0737731202 0.7540897691 0.6075590875 1.4373192190 0.9671123280 0.9534878387 1.4836242599 1.2273730192 0...
result:
ok 5625 numbers
Test #6:
score: 0
Accepted
time: 138ms
memory: 4092kb
input:
3600 5 114127 146710 467065 -311758 189643 449065 -303893 -215009 -789281 -140748 5 -449893 654165 -899120 -560520 719351 652759 285007 471281 987628 -767128 5 -587522 89736 -355416 -178001 801765 512722 314119 -136906 350051 762194 5 85697 920768 161507 -533920 -536515 401333 -27632 -987465 112237 ...
output:
84655.1995486339 270848.7268670296 202824.0367340314 135615.1918739256 119666.5085435029 89811.8707706889 254983.1535752974 189662.7472664882 64951.6570894377 154748.4422910088 214519.6820790192 163467.5328002302 278857.2574408529 191490.4979057995 172625.5296426240 144947.5248147898 232735.62583867...
result:
ok 3600 numbers
Test #7:
score: 0
Accepted
time: 128ms
memory: 4048kb
input:
3600 5 2 6 -6 4 4 0 -5 0 3 1 5 0 3 5 -5 2 6 4 0 2 -4 5 2 -2 -6 -3 -5 -5 -1 3 -4 0 5 0 6 -3 -5 5 1 4 -3 -5 6 5 0 -6 -6 -5 -2 6 1 6 2 0 5 2 1 6 5 4 -1 -3 -2 -6 4 5 -1 -2 5 -6 -1 4 -2 3 6 4 5 -6 3 6 -5 4 -4 3 -1 2 -6 5 5 -4 1 -5 1 0 5 -1 3 2 5 -4 6 2 -4 1 -4 5 5 -1 6 5 -3 0 0 6 -2 5 -5 5 2 6 5 2 -1 -4 ...
output:
1.3917338047 1.0600076621 1.3386604733 2.1786414884 1.8677635181 1.2550644197 1.8197054398 0.9463023056 1.1316433017 1.5772390611 0.5212123999 1.5371795538 0.9473384575 1.0470909720 0.5572297823 1.2085970170 1.2302893664 0.6675741417 0.3665059865 0.6943425277 0.5121414176 0.4362963750 0.8610973339 0...
result:
ok 3600 numbers
Test #8:
score: 0
Accepted
time: 133ms
memory: 3904kb
input:
3600 5 -3 1 0 -1 2 -3 4 1 5 0 5 -3 -5 1 -5 -2 -2 3 2 1 5 5 -4 -2 4 5 5 3 2 -4 -4 0 5 0 4 -5 3 1 4 -1 1 4 1 5 5 -3 2 -5 -3 -4 -1 1 5 1 5 -5 5 -2 1 -3 2 2 2 -4 5 5 -2 -3 -1 3 1 1 3 -2 -2 -2 5 2 1 -2 -3 -3 -3 5 0 -5 4 5 2 2 -2 5 5 -1 4 -5 -2 4 5 -4 5 -1 -3 -2 5 5 -1 -4 3 5 -5 -4 -1 -3 0 -1 -5 1 -4 -3 5...
output:
0.5433808490 1.2079312626 1.5754945621 0.8075181303 1.5566795740 0.6824490662 0.9074401042 0.9508389961 0.8537708709 1.3713082012 0.7426407751 0.4014915969 0.7474276060 0.4934691483 0.7112144829 0.6092998319 1.2344361488 0.4338148128 1.4679333256 0.6954624325 0.6914801531 0.8433199768 1.1987088726 1...
result:
ok 3600 numbers
Test #9:
score: 0
Accepted
time: 140ms
memory: 6116kb
input:
3600 5 0 2 3 -7 7 3 -6 -1 6 -6 5 -3 6 -5 6 -10 -2 -4 -8 -9 8 5 -2 2 2 -9 6 -3 2 10 -5 7 5 -7 9 9 -4 -8 -2 4 10 9 -8 5 -8 -5 -10 0 -7 0 0 -7 6 8 5 10 -7 8 -8 3 1 0 -4 -7 -4 5 2 -9 -3 1 -4 -2 -3 -3 0 1 5 -8 5 -10 6 2 -8 6 -5 -6 8 5 5 8 -8 -9 3 -7 -9 0 -4 3 5 2 -5 2 0 6 7 10 5 -8 -6 5 -10 -2 7 -6 -10 5...
output:
2.1052009095 1.5367686501 1.6070202283 3.5263473168 1.9784334680 1.0825185755 0.9461632076 1.6023271075 2.8837721402 0.9408148756 1.7013625613 1.6009202205 1.9334872323 0.6918659586 1.8339842711 0.6306479407 3.4339518703 2.4487067378 1.5516660596 1.1454890149 0.8735166647 1.5938651359 1.4443102714 2...
result:
ok 3600 numbers
Test #10:
score: 0
Accepted
time: 200ms
memory: 6120kb
input:
900 10 -10 -1 8 -6 7 -1 -5 8 -7 -9 4 -2 -9 10 -10 -8 9 9 -3 -6 10 -5 9 -7 -1 -9 -7 -4 6 -5 2 1 -4 10 8 -9 -9 2 0 7 7 10 -3 -7 9 -4 -5 2 1 1 6 7 -4 7 4 -6 0 1 -8 -5 3 -5 10 -3 -10 -8 -7 -5 -5 -6 3 -3 -1 7 -9 1 -5 9 -7 -2 3 -4 9 10 0 1 -3 8 -3 7 4 -10 10 -6 -5 -8 10 4 4 3 0 -8 3 -10 10 4 -5 2 0 -5 -10...
output:
2.6060274775 1.2633417725 1.1838990914 0.8827284671 1.8782272719 1.5698135706 1.5532952985 1.6328323301 1.5737994762 0.9970959561 0.9424829844 1.4172826182 1.4017665495 1.6939866361 2.8628778352 2.0553597643 2.2087768437 1.3202393648 1.5058644707 1.5958000817 1.9530554880 1.1865717598 1.0563282563 2...
result:
ok 900 numbers
Test #11:
score: 0
Accepted
time: 204ms
memory: 4068kb
input:
900 10 670067 394291 -797310 -637136 -435933 -923795 120936 309795 -934569 -688829 950758 634654 983083 900196 174829 181896 -191047 177910 258020 672165 10 424046 -657491 391198 -14995 -302986 -597011 -96387 -486090 -164032 -356501 -891789 12548 -703186 -924511 808215 -212606 659523 490088 738901 5...
output:
81290.1618383761 91483.7331961411 100154.0270558422 192606.4148202983 177441.6474344105 76150.8923721573 177358.7053738632 230115.8792668067 280209.2628450188 61218.5430212702 137504.7916377219 168344.5440410816 162167.1818149082 133102.5292692251 177087.4563457221 163543.6097759946 184494.309868969...
result:
ok 900 numbers
Test #12:
score: 0
Accepted
time: 271ms
memory: 4188kb
input:
225 20 -4 -9 -5 3 7 -10 10 7 2 7 1 4 2 2 -5 -1 -9 -1 -3 10 -8 -6 0 -5 7 -4 -6 -8 -7 -5 -1 -7 -1 -3 8 -6 6 3 8 2 20 8 2 6 -8 -3 -6 -2 9 5 -2 0 8 8 0 -7 -9 3 1 4 -10 4 7 -6 -1 -8 -7 2 -8 -8 -1 1 -9 2 -10 1 2 -7 8 -10 3 20 5 8 0 -3 9 -9 -10 -4 -10 -2 9 10 -2 8 -6 -10 6 -6 -3 7 5 10 7 7 -5 -6 -2 3 -4 0 ...
output:
0.6127869848 1.1137907182 0.7615364126 1.3308058885 0.7540492120 1.3328379607 0.6703147809 1.0353127837 0.9068174078 0.9769666614 0.7502848865 0.7780315596 0.7179049112 0.5715802085 0.7721060853 0.7692910081 1.8904459886 0.8600960487 1.0777332318 1.3129810811 0.8016468248 0.8696199191 0.8573236530 1...
result:
ok 225 numbers
Test #13:
score: 0
Accepted
time: 280ms
memory: 4192kb
input:
225 20 983700 -466859 -20884 -364855 807044 -308568 -785298 910840 -61173 -276993 -872226 -878552 -235162 831941 978289 938037 585612 -598517 545857 403231 -450887 -558997 -293044 -675226 -900628 102932 -836719 -530135 -534412 -681687 -487340 -227869 161252 -557533 397943 464720 170537 68556 413322 ...
output:
103902.0526005441 185063.0384573450 60443.6573723248 118360.3646096438 157018.7851307629 103511.4658062259 65549.6994792792 67043.3588288711 105010.2705326675 93450.0576684343 96005.2282075878 54350.0986013002 134718.5353431164 98397.3545701079 71213.2949663550 77465.3939447420 75212.0930407925 1236...
result:
ok 225 numbers
Test #14:
score: 0
Accepted
time: 79ms
memory: 4400kb
input:
6 50 -107573 -479674 -523931 117259 705403 519626 -802569 -162243 510741 876735 206326 -333274 448335 -276206 482965 -837837 873180 -965235 -359525 608790 -53827 782310 689038 -718590 739597 111296 420387 -953079 -492679 -243600 -929509 1174 800731 -968797 208236 193620 249265 499134 848153 771472 5...
output:
20480.3828539945 21190.0221497536 27821.6725958609 28113.3193405147 27223.9676079317 31857.8357100237
result:
ok 6 numbers
Test #15:
score: 0
Accepted
time: 379ms
memory: 4412kb
input:
36 50 569818 -279771 972561 928848 383 744221 -453534 -154445 293032 502859 744851 436690 293077 503053 657 744258 317135 -276665 293067 502799 277103 -439313 282010 -387735 276848 -439025 972274 928763 -110443 -507380 744799 436605 282061 -387926 -453689 -154326 317468 -276534 -453630 -154510 28193...
output:
81019.4274543921 77527.2587729629 55029.2464233119 42253.1543856355 72715.8578229821 197374.6307406388 37469.7225819169 66130.3529953631 54454.5978064967 125611.0883685123 71800.2062730490 87529.3367687952 143932.8876147661 95010.1346814902 86801.3479384900 106229.4888661041 99367.3086457716 93764.6...
result:
ok 36 numbers
Test #16:
score: 0
Accepted
time: 349ms
memory: 4396kb
input:
36 50 -767165 583573 -284890 -681002 -423448 -259226 -285077 -680913 -921552 -557651 -767105 583853 -423314 -259380 790075 -225214 -921537 -557431 -767305 583770 -767124 583508 -921629 -557448 -423530 -259463 -284954 -680837 -423426 -259294 -423469 -259099 -767302 583744 -921772 -557672 -423503 -259...
output:
36643.6054805936 73491.0580576342 355454.4402131349 76283.4915153242 114070.2207770458 102751.9423399158 346834.5085962089 142611.0579378523 246800.0671139018 131055.8866665811 22279.8879892140 215589.6576250780 83424.8688141581 51800.2345429414 43278.8616878964 278223.4837556020 81405.2167205066 25...
result:
ok 36 numbers
Test #17:
score: 0
Accepted
time: 353ms
memory: 4396kb
input:
36 50 -757926 470127 -757550 470454 250422 -395772 250548 -395869 568164 -704082 250417 -396082 -757845 470427 444672 170989 250387 -395875 250484 -395866 568177 -704202 -757558 470484 250530 -395763 250488 -395883 -757754 470201 250529 -396062 -757760 470255 568050 -704413 444991 171218 444963 1710...
output:
41461.4157312312 61470.3459020843 198910.9999673769 35019.3686454291 139342.5797078109 26339.6628390343 247086.6792489548 108103.8329786103 269038.9700572530 40491.2267640828 99838.8739582890 174035.1497371408 172811.2119707150 155604.8803016135 30013.6705970499 250614.3951947112 84144.5624718379 20...
result:
ok 36 numbers
Test #18:
score: 0
Accepted
time: 473ms
memory: 4940kb
input:
9 100 -79487 826724 571284 354748 -312616 727781 -838024 249391 -79475 826592 796988 -514208 -847898 -839919 584481 896431 -847899 -839656 -312680 727782 22798 138363 466409 -215121 -36729 -925283 677267 -733543 -789119 581936 -789111 581860 271104 629366 571356 354824 -946155 -832752 571238 354954 ...
output:
23149.7505948995 20131.1691208430 50752.3036752972 22743.2512424825 21418.0199422366 24609.1329750448 20676.5752705816 23043.7559151699 35012.2203029409
result:
ok 9 numbers
Test #19:
score: 0
Accepted
time: 1ms
memory: 4116kb
input:
1 10 2 -999 3 -998 4 -995 5 -990 6 -983 7 -974 8 -963 9 -950 1000 1000 -1000 1000
output:
293.8271086913
result:
ok found '293.8271087', expected '293.8271087', error '0.0000000'
Test #20:
score: 0
Accepted
time: 1299ms
memory: 9132kb
input:
1 300 -1000000 700000 -999999 697990 -999998 695960 -999997 693910 -999996 691840 -999995 689750 -999994 687640 -999993 685510 -999992 683360 -999991 681190 -999990 679000 -999989 676790 -999988 674560 -999987 672310 -999986 670040 -999985 667750 -999984 665440 -999983 663110 -999982 660760 -999981 ...
output:
46.7179453520
result:
ok found '46.7179454', expected '46.7179454', error '0.0000000'
Test #21:
score: 0
Accepted
time: 1094ms
memory: 9148kb
input:
1 300 -9999 -2 -9998 -3 -9995 -4 -9990 -5 -9983 -6 -9974 -7 -9963 -8 -9950 -9 -9935 -10 -9918 -11 -9899 -12 -9878 -13 -9855 -14 -9830 -15 -9803 -16 -9774 -17 -9743 -18 -9710 -19 -9675 -20 -9638 -21 -9599 -22 -9558 -23 -9515 -24 -9470 -25 -9423 -26 -9374 -27 -9323 -28 -9270 -29 -9215 -30 -9158 -31 -9...
output:
2367.6921379694
result:
ok found '2367.6921380', expected '2367.6921380', error '0.0000000'
Test #22:
score: 0
Accepted
time: 1291ms
memory: 8896kb
input:
1 300 700000 1000000 697990 999999 695960 999998 693910 999997 691840 999996 689750 999995 687640 999994 685510 999993 683360 999992 681190 999991 679000 999990 676790 999989 674560 999988 672310 999987 670040 999986 667750 999985 665440 999984 663110 999983 660760 999982 658390 999981 656000 999980...
output:
46.7179453565
result:
ok found '46.7179454', expected '46.7179454', error '0.0000000'
Test #23:
score: 0
Accepted
time: 1210ms
memory: 9056kb
input:
1 300 -2 9999 -3 9998 -4 9995 -5 9990 -6 9983 -7 9974 -8 9963 -9 9950 -10 9935 -11 9918 -12 9899 -13 9878 -14 9855 -15 9830 -16 9803 -17 9774 -18 9743 -19 9710 -20 9675 -21 9638 -22 9599 -23 9558 -24 9515 -25 9470 -26 9423 -27 9374 -28 9323 -29 9270 -30 9215 -31 9158 -32 9099 -33 9038 -34 8975 -35 8...
output:
2367.6921379535
result:
ok found '2367.6921380', expected '2367.6921380', error '0.0000000'
Test #24:
score: 0
Accepted
time: 1285ms
memory: 9092kb
input:
1 300 1000000 -700000 999999 -697990 999998 -695960 999997 -693910 999996 -691840 999995 -689750 999994 -687640 999993 -685510 999992 -683360 999991 -681190 999990 -679000 999989 -676790 999988 -674560 999987 -672310 999986 -670040 999985 -667750 999984 -665440 999983 -663110 999982 -660760 999981 -...
output:
46.7179453488
result:
ok found '46.7179453', expected '46.7179454', error '0.0000000'
Test #25:
score: 0
Accepted
time: 1174ms
memory: 9088kb
input:
1 300 9999 2 9998 3 9995 4 9990 5 9983 6 9974 7 9963 8 9950 9 9935 10 9918 11 9899 12 9878 13 9855 14 9830 15 9803 16 9774 17 9743 18 9710 19 9675 20 9638 21 9599 22 9558 23 9515 24 9470 25 9423 26 9374 27 9323 28 9270 29 9215 30 9158 31 9099 32 9038 33 8975 34 8910 35 8843 36 8774 37 8703 38 8630 3...
output:
2367.6921379601
result:
ok found '2367.6921380', expected '2367.6921380', error '0.0000000'
Test #26:
score: 0
Accepted
time: 709ms
memory: 9008kb
input:
1 300 -700000 -1000000 -697990 -999999 -695960 -999998 -693910 -999997 -691840 -999996 -689750 -999995 -687640 -999994 -685510 -999993 -683360 -999992 -681190 -999991 -679000 -999990 -676790 -999989 -674560 -999988 -672310 -999987 -670040 -999986 -667750 -999985 -665440 -999984 -663110 -999983 -6607...
output:
46.7179453508
result:
ok found '46.7179454', expected '46.7179454', error '0.0000000'
Test #27:
score: 0
Accepted
time: 1183ms
memory: 8952kb
input:
1 300 2 -999999 3 -999998 4 -999995 5 -999990 6 -999983 7 -999974 8 -999963 9 -999950 10 -999935 11 -999918 12 -999899 13 -999878 14 -999855 15 -999830 16 -999803 17 -999774 18 -999743 19 -999710 20 -999675 21 -999638 22 -999599 23 -999558 24 -999515 25 -999470 26 -999423 27 -999374 28 -999323 29 -9...
output:
24.9160640993
result:
ok found '24.9160641', expected '24.9160641', error '0.0000000'
Test #28:
score: 0
Accepted
time: 1053ms
memory: 9000kb
input:
1 300 2 -44999 3 -44998 4 -44995 5 -44990 6 -44983 7 -44974 8 -44963 9 -44950 10 -44935 11 -44918 12 -44899 13 -44878 14 -44855 15 -44830 16 -44803 17 -44774 18 -44743 19 -44710 20 -44675 21 -44638 22 -44599 23 -44558 24 -44515 25 -44470 26 -44423 27 -44374 28 -44323 29 -44270 30 -44215 31 -44158 32...
output:
479.3020660438
result:
ok found '479.3020660', expected '479.3020661', error '0.0000000'
Test #29:
score: 0
Accepted
time: 1200ms
memory: 9008kb
input:
1 300 2 -9999 3 -9998 4 -9995 5 -9990 6 -9983 7 -9974 8 -9963 9 -9950 10 -9935 11 -9918 12 -9899 13 -9878 14 -9855 15 -9830 16 -9803 17 -9774 18 -9743 19 -9710 20 -9675 21 -9638 22 -9599 23 -9558 24 -9515 25 -9470 26 -9423 27 -9374 28 -9323 29 -9270 30 -9215 31 -9158 32 -9099 33 -9038 34 -8975 35 -8...
output:
2367.6921379652
result:
ok found '2367.6921380', expected '2367.6921380', error '0.0000000'
Test #30:
score: 0
Accepted
time: 1175ms
memory: 9136kb
input:
1 300 2 -49999 3 -49998 4 -49995 5 -49990 6 -49983 7 -49974 8 -49963 9 -49950 10 -49935 11 -49918 12 -49899 13 -49878 14 -49855 15 -49830 16 -49803 17 -49774 18 -49743 19 -49710 20 -49675 21 -49638 22 -49599 23 -49558 24 -49515 25 -49470 26 -49423 27 -49374 28 -49323 29 -49270 30 -49215 31 -49158 32...
output:
7347.5787737187
result:
ok found '7347.5787737', expected '7347.5787737', error '0.0000000'
Test #31:
score: 0
Accepted
time: 1193ms
memory: 9012kb
input:
1 300 2 -99999 3 -99998 4 -99995 5 -99990 6 -99983 7 -99974 8 -99963 9 -99950 10 -99935 11 -99918 12 -99899 13 -99878 14 -99855 15 -99830 16 -99803 17 -99774 18 -99743 19 -99710 20 -99675 21 -99638 22 -99599 23 -99558 24 -99515 25 -99470 26 -99423 27 -99374 28 -99323 29 -99270 30 -99215 31 -99158 32...
output:
7264.8235486766
result:
ok found '7264.8235487', expected '7264.8235487', error '0.0000000'
Test #32:
score: 0
Accepted
time: 787ms
memory: 8960kb
input:
1 300 2 -999999 3 -999998 4 -999995 5 -999990 6 -999983 7 -999974 8 -999963 9 -999950 10 -999935 11 -999918 12 -999899 13 -999878 14 -999855 15 -999830 16 -999803 17 -999774 18 -999743 19 -999710 20 -999675 21 -999638 22 -999599 23 -999558 24 -999515 25 -999470 26 -999423 27 -999374 28 -999323 29 -9...
output:
80244.5137404414
result:
ok found '80244.5137404', expected '80244.5137404', error '0.0000000'
Test #33:
score: 0
Accepted
time: 1745ms
memory: 9140kb
input:
1 300 -582688 -338066 65950 664506 726195 -342195 778617 -357210 -854288 556277 300499 294357 643715 884595 145808 699895 823594 197029 -326906 -938477 -635849 -984773 -133686 656789 -435448 690719 903384 -472986 82595 315750 -162788 541714 -77694 -237304 -850565 -426412 248922 -808508 -719332 -6663...
output:
1478.8300558656
result:
ok found '1478.8300559', expected '1478.8300559', error '0.0000000'
Test #34:
score: 0
Accepted
time: 1427ms
memory: 9144kb
input:
1 300 329399 -774056 -453420 -971922 -963389 -692906 -901061 -690960 -954671 -555749 954332 -856245 97920 127454 422794 -72309 402518 -482396 -274243 -242236 -63992 224700 841180 586025 -266496 -824730 -178245 -230280 680876 907784 553835 674598 89593 396532 143208 -684880 538608 -578116 -422477 757...
output:
972.4232802278
result:
ok found '972.4232802', expected '972.4232802', error '0.0000000'
Test #35:
score: 0
Accepted
time: 1335ms
memory: 9108kb
input:
1 300 -360611 262745 -266788 208188 -959303 -907228 -443316 -204307 682906 -640611 -629502 -217089 -323067 -687634 437059 491032 -924621 882842 844758 667473 765630 -661241 -192156 -841346 -154832 -812793 -47327 10282 -597348 957691 892586 942751 142330 937555 953415 -727776 -605831 643868 -310790 -...
output:
1247.6354475703
result:
ok found '1247.6354476', expected '1247.6354476', error '0.0000000'
Test #36:
score: 0
Accepted
time: 1348ms
memory: 9088kb
input:
1 300 -206748 733504 405233 346961 -313290 -216319 -485737 -231831 -164104 165946 -515020 -589364 982156 -80607 873259 619605 -482416 -888108 -569548 252891 -445640 901994 985477 -967333 42455 -483916 73904 760015 -943641 942808 396828 484027 -841584 -24224 -175993 952815 790566 541282 -279849 -3442...
output:
999.0193963582
result:
ok found '999.0193964', expected '999.0193964', error '0.0000000'
Test #37:
score: 0
Accepted
time: 1500ms
memory: 9140kb
input:
1 300 580502 -850604 -828356 778 184624 -535893 -697221 -969976 896503 -655248 -76966 -243055 60920 160544 44843 -658551 -447963 886466 278568 389553 -623912 -127161 678049 -413324 -430351 -318993 -817724 -933164 -711215 340590 -74113 689203 68654 -100261 182253 786353 970301 867792 -749733 -811174 ...
output:
842.0590723713
result:
ok found '842.0590724', expected '842.0590724', error '0.0000000'
Test #38:
score: 0
Accepted
time: 1476ms
memory: 9196kb
input:
1 300 -316120 -118763 45309 190875 409669 -105265 -506284 573308 -516833 322648 -866719 -936225 -12677 -985703 711314 569209 941787 83443 -514860 686132 -790586 -545380 430362 -424821 -833415 938854 -942534 683223 -240135 606924 -403050 269157 -215947 985881 -549116 600378 459464 -595098 725250 1147...
output:
1024.4978698409
result:
ok found '1024.4978698', expected '1024.4978698', error '0.0000000'
Test #39:
score: 0
Accepted
time: 1187ms
memory: 9148kb
input:
1 300 -173407 -202877 781435 -868900 -708456 340380 -576940 717700 182725 270819 936854 705842 -558936 563953 -442817 -537862 456021 536960 -280357 -280460 865334 142839 774139 179758 441597 150328 97859 -980348 -33644 644740 -930102 492073 -672777 225390 567301 -123428 272474 613299 939529 -568972 ...
output:
999.8589008248
result:
ok found '999.8589008', expected '999.8589008', error '0.0000000'
Test #40:
score: 0
Accepted
time: 1665ms
memory: 9032kb
input:
1 300 -345250 -831776 -186776 -708481 -461210 345548 -813591 339981 875529 -243454 -612714 -565349 342248 -74704 440632 -335722 -680195 541251 -40910 -905178 644877 899186 274573 743026 873540 -442740 535392 952686 797733 860447 -20479 505758 -951532 613082 -890210 663776 767606 -285569 466835 86332...
output:
931.0523112101
result:
ok found '931.0523112', expected '931.0523112', error '0.0000000'
Test #41:
score: 0
Accepted
time: 1582ms
memory: 9088kb
input:
1 300 370249 -59123 -776101 -977670 -243135 -532403 -579041 96635 569778 -862215 413939 -366298 481224 272525 393367 -40979 483831 994010 -233019 628811 -143918 477955 339126 11331 -107685 517540 622176 -412060 -177324 -205192 431089 749790 -95536 -210836 548410 -707079 616094 -127500 -783278 -72261...
output:
933.7604866928
result:
ok found '933.7604867', expected '933.7604867', error '0.0000000'
Test #42:
score: 0
Accepted
time: 1612ms
memory: 9148kb
input:
1 300 572725 -213611 493742 -808213 -710052 -380510 893881 -474967 9640 -788263 -459353 580756 -26412 638961 440498 -802856 453695 -912107 22051 -399011 547574 755649 -686907 874963 -504322 -340049 692117 -724428 668948 874184 48863 726276 -663172 -738633 360506 985895 589965 723490 -791113 -581246 ...
output:
1077.8413806349
result:
ok found '1077.8413806', expected '1077.8413807', error '0.0000000'
Test #43:
score: 0
Accepted
time: 1470ms
memory: 8888kb
input:
1 300 -18347 947891 -18966 947674 -18153 949129 371892 55936 -19040 948495 -19316 948666 -19369 949236 -18720 948324 -19293 949610 -17823 949522 -19243 948220 -18639 948552 -17649 949411 371651 54266 -19228 948586 -17602 948463 -19485 949188 -18243 948112 -17773 948743 372205 54093 -18298 949126 371...
output:
430.9016508304
result:
ok found '430.9016508', expected '430.9016509', error '0.0000000'
Test #44:
score: 0
Accepted
time: 1531ms
memory: 9144kb
input:
1 300 -74242 456694 -526886 299650 -74220 457055 -73487 456305 -73859 456656 61507 -819056 60998 -819121 -526707 299370 -526276 300041 61552 -817655 -526738 299576 -74124 456791 -527186 299008 61978 -818405 -74813 455682 60560 -819145 -73451 455525 -74892 457185 -73693 456477 60721 -818196 60214 -81...
output:
90267.0931341244
result:
ok found '90267.0931341', expected '90267.0931341', error '0.0000000'
Test #45:
score: 0
Accepted
time: 1094ms
memory: 8936kb
input:
1 300 574585 394710 574622 393610 -423278 771639 -424926 771360 -424084 771410 -355381 -781788 -355711 -782971 573941 394518 -356559 -782641 -356747 -782401 468958 -215431 -423584 771961 574237 394615 -423230 771874 574235 394702 -424141 771353 -423250 771823 469278 -214864 -423677 771854 470643 -21...
output:
217408.1481352935
result:
ok found '217408.1481353', expected '217408.1481353', error '0.0000000'
Test #46:
score: 0
Accepted
time: 1279ms
memory: 8816kb
input:
1 300 426446 450150 704880 -177836 705023 -177943 365125 -787336 426646 450111 365336 -787509 -488479 191560 365230 -787626 351178 85715 426393 450079 426499 450252 350929 85788 351095 85697 350955 85774 351185 85404 426289 450343 -488469 191487 365412 -787578 351069 85754 -488205 191341 365332 -787...
output:
20170.8709063751
result:
ok found '20170.8709064', expected '20170.8709064', error '0.0000000'
Test #47:
score: 0
Accepted
time: 915ms
memory: 9016kb
input:
1 300 -400243 814451 22608 892635 -400101 814103 6514 778975 993334 -477496 6342 779132 462061 255284 -51701 297766 22472 892564 340929 -448021 479819 -339231 -400286 814390 211825 26983 6556 779317 993060 -477289 993308 -477342 -51535 297899 340706 -447842 340883 -447854 -400416 814256 -400283 8141...
output:
9230.4423163080
result:
ok found '9230.4423163', expected '9230.4423163', error '0.0000000'
Test #48:
score: 0
Accepted
time: 802ms
memory: 9024kb
input:
1 300 -474014 -864992 -630838 -307407 -630606 -307503 -124096 -743059 -771964 728691 772586 240106 -772183 728879 391413 526273 199846 912927 428389 -576556 -308290 579377 -255160 -108840 772406 240313 -367068 -161358 772571 240365 -308290 579342 391393 526479 -415239 -4737 -367131 -161451 199868 91...
output:
15025.9748438052
result:
ok found '15025.9748438', expected '15025.9748438', error '0.0000000'
Test #49:
score: 0
Accepted
time: 1018ms
memory: 9004kb
input:
1 300 50620 -400031 50739 -399860 510490 905605 -231850 -472272 819819 -32769 556769 430166 510572 905474 -835681 -521539 -892931 517162 308414 643333 726593 422199 864670 -884154 -923273 383788 405709 273425 -479932 -974056 410500 738923 186655 767275 -182443 950085 -567600 -112887 603101 210566 93...
output:
3406.4535451969
result:
ok found '3406.4535452', expected '3406.4535452', error '0.0000000'
Test #50:
score: 0
Accepted
time: 1407ms
memory: 9004kb
input:
1 300 176452 -329206 -579449 737212 -127383 552242 979657 -356153 80368 -694513 460265 -812959 445149 141242 -457009 -165865 607661 133016 -790741 -28932 833272 -591475 -579288 737176 -259244 232127 -387178 -302780 176289 -329051 -581332 414202 130425 339972 280492 -57804 -23731 -362222 -538093 -596...
output:
1990.3405678490
result:
ok found '1990.3405678', expected '1990.3405679', error '0.0000000'
Test #51:
score: 0
Accepted
time: 1377ms
memory: 9012kb
input:
1 300 1000000 0 999780 20942 999122 41875 998026 62790 996492 83677 994521 104528 992114 125333 989272 146083 985996 166768 982287 187381 978147 207911 973578 228350 968583 248689 963162 268919 957319 289031 951056 309016 944376 328866 937281 348572 929776 368124 921863 387515 913545 406736 904827 4...
output:
499972.2525363024
result:
ok found '499972.2525363', expected '499972.2525363', error '0.0000000'
Test #52:
score: 0
Accepted
time: 1445ms
memory: 8928kb
input:
1 299 1000000 0 999111 42156 996445 84238 992008 126169 985807 167877 977854 209286 968162 250323 956748 290915 943634 330989 928842 370475 912398 409303 894332 447402 874676 484707 853465 521149 830736 556665 806531 591191 780891 624666 753863 657030 725495 688227 695837 718199 664941 746895 632864...
output:
208109.8148594101
result:
ok found '208109.8148594', expected '208109.8148594', error '0.0000000'