QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#735217 | #5104. Guardians of the Gallery | BananaMac | AC ✓ | 129ms | 4128kb | C++20 | 14.3kb | 2024-11-11 18:25:30 | 2024-11-11 18:25:34 |
Judging History
answer
/**
* 10:43:50 11/11/24
* point_vis
*/
// ./ICPC/Geometry/OrganizedTemplates/point_vis.cpp
//#include "Point.cpp"
/**
* 15:15:28 9/27/24
* Point
*/
// ./ICPC/Geometry/OrganizedTemplates/Point.cpp
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define uint unsigned int
#define double long double
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define nl '\n'
#define all(v) v.begin(), v.end()
#define NO (cout << "NO" << nl);
#define YES (cout << "YES" << nl);
#define F first
#define S second
#define INF LONG_LONG_MAX
#define MOD 1000000007ll
#define EPS 1e-9l
#define PI 3.14159265358979323846264338327950288L
#define pii pair<int, int>
#define X real()
#define Y imag()
#define vec vector
#define LT int T; cin >> T; while (T--)
template<typename T>
using vec2d = vector<vector<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
using indexed_set = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
namespace Geometry {
using ftype = double;
using atype = double;
const double eps = 1e-9l;
const double pi = acos(-1.0l);
const double e = exp(1.0L);
const double inf = INF;
const int iinf = LONG_LONG_MAX;
const int prec = 25;
ftype sqr(ftype v) { return v * v; }
void setPrec(ostream& out = cout) {
out << fixed << setprecision(prec);
}
//bool eq(const ftype& a, const ftype& b) {
// return a == b;
//}
bool eq(const ftype& a, const ftype& b) {
return abs(a - b) < eps;
}
//bool ls(const ftype& a, const ftype& b) {
// return a < b;
//}
bool ls(const ftype& a, const ftype& b) {
return (b - a) > eps;
}
//bool lse(const ftype& a, const ftype& b) {
// return a <= b;
//}
bool lse(const ftype& a, const ftype& b) {
return ls(a, b) or eq(a, b);
}
//bool gt(const ftype& a, const ftype& b) {
// return a > b;
//}
bool gt(const ftype& a, const ftype& b) {
return not ls(a, b) and not eq(a, b);
}
// Returns angle with respect to the x-axis.
atype angle(atype x, atype y) {
return atan2(y, x);
}
atype torad(atype a) { return a / 180 * pi; }
atype todeg(atype a) { return a / pi * 180; }
int sign(const ftype& v) {
if (ls(0, v)) return 1;
else if (ls(v, 0)) return -1;
return 0;
}
// Orientation of 3 points forming an angle
enum class Orientation {
l = 1,
r = -1,
c = 0
};
// 2D point
struct P {
ftype x, y;
static P polar(const ftype& r, const atype& a) {
return {r * cos(a), r * sin(a)};
}
P(): x{0}, y{0} {}
P(ftype x, ftype y): x{x}, y{y} {}
explicit P(const complex<ftype>& p): P(p.real(), p.imag()) {}
explicit P(const pair<ftype, ftype>& p): P(p.F, p.S) {}
P(const P& p): P(p.x, p.y) {}
explicit operator complex<ftype>() const {
return {x, y};
}
explicit operator pair<ftype, ftype>() const {
return {x, y};
}
ftype dist(const P& p) const {
return (*this - p).abs();
}
atype r() const {
return hypot(x, y);
}
atype a() const {
return angle(x, y);
}
atype ua(const P& p) const {
// undirected angle
double v0 = fabs(a() - p.a()), v1 = fabs(p.ap() - ap());
if (ls(v0, v1)) return v0;
else return v1;
}
atype ap() const {
atype res = angle(x, y);
if (res < 0) res += 2 * pi;
return res;
}
P operator-() const {
return *this * -1;
}
P operator+() const {
return *this;
}
P operator+=(const P& p) {
x += p.x;
y += p.y;
return *this;
}
P operator-=(const P& p) {
x -= p.x;
y -= p.y;
return *this;
}
P operator*=(const ftype& v) {
x *= v;
y *= v;
return *this;
}
P operator/=(const ftype& v) {
x /= v;
y /= v;
return *this;
}
P operator%=(const ftype& v) {
x = fmod(x, v);
y = fmod(y, v);
return *this;
}
P operator^=(const ftype& an) {
return *this = rotateccw(an);
}
P operator|=(const ftype& an) {
return *this = rotatecw(an);
}
P operator|(const ftype& an) {
P res = *this;
res |= an;
return res;
}
P operator^(const ftype& an) {
P res = *this;
res ^= an;
return res;
}
P operator+(const P& p) const {
P res = *this;
res += p;
return res;
}
P operator-(const P& p) const {
P res = *this;
res -= p;
return res;
}
P operator*(const ftype& v) const {
P res = *this;
res *= v;
return res;
}
P operator/(const ftype& v) const {
P res = *this;
res /= v;
return res;
}
P operator%(const ftype& v) const {
P res = *this;
res %= v;
return res;
}
bool operator==(const P& p) const {
return eq(x, p.x) and eq(y, p.y);
}
bool operator<(const P& p) const {
return eq(p.x, x) ? ls(y, p.y) : ls(x, p.x);
}
bool operator<=(const P& p) const {
return *this < p or *this == p;
}
ftype cross(const P& b, const P& c) const {
return (b - *this).cross(c - *this);
}
Orientation orientation(const P& pb, const P& pc) const {
const P& pa = *this;
ftype d = (pb - pa).cross(pc - pa);
return static_cast<Orientation>(
ls(0, d) - ls(d, 0)
);
}
ftype cross(const P& p) const {
return x * p.y - y * p.x;
}
ftype dot(const P& p) const {
return x * p.x + y * p.y;
}
ftype norm() const {
return dot(*this);
}
atype abs() const {
return sqrt((atype)norm());
}
P truncate(ftype v) const {
// returns a vector with norm v and having same direction
ftype k = abs();
if (sign(k) == 0) return *this;
v /= k;
return {x * v, y * v};
}
P normalize() const {
return truncate(1);
}
P normal_l() const {
return {-y, x};
}
P normal_r() const {
return {y, -x};
}
P rotateccw(const atype& angle, const P& ref = {0, 0}) const {
P res;
ftype xs = x - ref.x, ys = y - ref.y;
res.x = ref.x + (xs * cos(angle) - ys * sin(angle));
res.y = ref.y + (xs * sin(angle) + ys * cos(angle));
return res;
}
P rotatecw(const atype& angle, const P& ref = {0, 0}) const {
return rotateccw(-angle, ref);
}
friend P operator*(const ftype& v, const P& p) {
return p * v;
}
friend istream& operator>>(istream& in, P& p) {
int xv, yv;
in >> xv >> yv;
p = P(xv, yv);
return in;
}
friend ostream& operator<<(ostream& out, const P& p) {
setPrec(out);
return out << "(" << p.x << ", " << p.y << ")";
}
};
// basic comparison functions
auto angleCmp = [](const P& p0, const P& p1) -> bool {
return ls(p0.a(), p1.a());
};
auto radiusCmp = [](const P& p0, const P& p1) -> bool {
return ls(p0.r(), p1.r());
};
auto stdCmp = [](const P& p0, const P& p1) -> bool {
return p0 < p1;
};
auto xCmp = [](const P& p0, const P& p1) -> bool {
return ls(p0.x, p1.x);
};
auto yCmp = [](const P& p0, const P& p1) -> bool {
return ls(p0.y, p1.y);
};
// Hash function
struct p_hash {
static __int128 splitmix128(__int128 x) {
// gr = 0x9e3779b97f4a7c15f39cc0605cedc835
// c0 = 0xbf58476d1ce4e5b9a3f7b72c1e3c9e3b
// c1 = 0x94d049bb133111ebb4093822299f31d7
__int128 gr = 0x9e3779b97f4a7c15, c0 = 0xbf58476d1ce4e5b9, c1 = 0x94d049bb133111eb;
gr <<= 64;
c0 <<= 64;
c1 <<= 64;
gr += 0xf39cc0605cedc835;
c0 += 0xa3f7b72c1e3c9e3b;
c1 += 0xb4093822299f31d7;
x += gr;
x = (x ^ (x >> 62)) * c0;
x = (x ^ (x >> 59)) * c1;
return x ^ (x >> 63);
}
size_t operator()(const P& p) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
__int128 x = (((__int128)p.x) << 64) | ((__int128)p.y);
return splitmix128(x + FIXED_RANDOM);
}
};
}
using namespace Geometry;
//如果两个向量的叉积结果符号相反(一个为正,一个为负),则说明线段AC和线段AD在线段AB的两侧,即线段AC和线段AD相交。
double RayIntersect(const P& a, const P& b, const P& c, const P& d, int* sides = NULL) {
double cp1 = (c-a).cross(b-a), cp2 = (d-a).cross(b-a);
double dp1 = (c-a).dot(b-a), dp2 = (d-a).dot(b-a);
if (sides) *sides = (cp1 < -eps || cp2 < -eps) + 2 * (cp1 > eps || cp2 > eps);//sides 0,1,2,3,如果两个线段相交,一定是3 1,2是ab直线穿过c或者d的情况
if (cp1 < -eps && cp2 < -eps || cp1 > eps && cp2 > eps) return -1.0;//叉积结果同号,线段不相交
return (abs(cp1) < eps && abs(cp2) < eps) ? 0 : (dp1*cp2-dp2*cp1)/(cp2-cp1);//a到交点的距离乘以ab长度
}
bool POnLine(const P& a, const P& b, const P& p) {
double ln = (b-a).abs(), cp = (b-a).cross(p-a), dp = (b-a).dot(p-a);
return abs(cp/ln) < eps && dp/ln > -eps && dp/ln < ln+eps;//cp=0 && 0<dp<ln^2
}
int32_t main(){
int n;
cin>>n;
vector<P> polygon(n);
P s,g;
for (int i = 0; i < n; ++i) {
cin>>polygon[i];
}
cin>>g>>s;
vector<P> endpoints;
//找指向每个顶点方向距离最近的intersecting边
polygon.push_back(g);//g点方向也需要找
for(auto p:polygon){
vector<tuple<double,int>> intersections;//交点距离,遮挡面
if((p-s).abs()<eps)continue;
p=(p-s)/(p-s).abs()+s;
//找出sculpture向各个顶点出发, 不被遮挡能走的最远距离maxd,即视野不被遮挡的区域的终点(在多边形的边上)
for(int i=0;i<n;++i){
int side=0;
auto d= RayIntersect(s,p,polygon[i],polygon[(i+1)%n],&side);
if(d>-eps)
intersections.emplace_back(d,side);
}
ranges::sort(intersections);
double maxd=0;
int sides=0;
for(auto [d,s]:intersections){
maxd=d;
sides|=s;
if(sides==3)break;
}
endpoints.push_back(s+(p-s)*maxd);//从sculpture出发,沿着射线,视野不被遮挡的区域的终点(在多边形的边上)
//计算顶点p2,到sculpture发出的穿过顶点i的射线,的距离,以及交点
for(auto p2:polygon){
auto ortho=P(s.y-p.y,p.x-s.x)*1e5;
auto d= RayIntersect(s,p,p2,p2+ortho);
if(d<-eps)
d= RayIntersect(s,p,p2,p2-ortho);
if(d>eps && d<maxd-eps)
endpoints.push_back(s+(p-s)*d);
}
}
polygon.pop_back();
//dijkstra算法求最短长度
vector<P> points(polygon.size()+2+endpoints.size());
int i=0;
points[i++]=g;
for(auto p:polygon)points[i++]=p;
points[i++]=s;
for(auto p:endpoints)points[i++]=p;
priority_queue<pair<double,int>, vector<pair<double,int>>, greater<>> que;
vector<double> dist(points.size(),1e20);//从g到每个节点的最短路径长度
que.emplace(0.0,0);//从0号guard的起始位置出发
for(i=que.top().second;i<=n;i=que.top().second){
auto d=que.top().first;
assert(que.size());
que.pop();
if(d>=dist[i])continue;
dist[i]=d;
for(int j=0;j<points.size();++j){
if(i==j)continue;
auto p1=points[i], p2=points[j];
auto ln=(p1-p2).abs();
if(ln<eps ||
//如果j在poly顶点i关联的两条poly边上,可以直接沿着poly边走到j,不需要后面的包含性判断
i>=1&&i<=n && POnLine(polygon[i-1], polygon[(i) % n], p2) ||
i>=1&&i<=n && POnLine(polygon[i-1], polygon[(i + n - 2) % n], p2)) {
que.emplace(d+ln,j);
continue;
}
//判断p1p2是否被poly完全包含
bool fullContained=true;
p2=p1+(p2-p1)/ln;
for(int k=0;k<polygon.size();++k){
auto rd= RayIntersect(p1,p2,polygon[k],polygon[(k+1)%n]);
if(rd>eps && rd<ln-eps) {
fullContained=false;
break;
}
}
if(!fullContained)continue;
//判断一下p1p2上任意一点是不是在poly内部,来保证p1p2全段都在poly内部。通过p1p2中点画一任意射线, 看穿过poly为奇数还是偶数次
int cnt=0;
p1 = p1*2/3 + p2/ 3;
p2 = p1 + P(cos(10), sin(10));
for(int k=0;k<n;++k){
auto rd= RayIntersect(p1,p2,polygon[k],polygon[(k+1)%n]);
cnt+=(rd>eps);
}
if(cnt%2==1)
que.emplace(d+ln,j);
}
}
setPrec();
cout << que.top().first << nl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3976kb
input:
15 13 7 20 20 39 20 49 7 73 13 100 5 117 38 98 20 80 20 66 40 68 20 51 20 41 39 22 48 2 39 10 20 104 20
output:
29.0000000000000000000000000
result:
ok found '29.0000000', expected '29.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
16 39 2 48 22 39 41 20 51 20 68 40 66 20 80 20 98 38 117 5 100 13 73 7 49 19 39 20 23 20 20 7 13 20 10 20 104
output:
13.0000000000000000000000000
result:
ok found '13.0000000', expected '13.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3904kb
input:
16 13 33 20 60 23 66 39 97 49 105 73 166 100 205 117 272 98 216 80 180 66 172 68 156 51 122 41 121 22 92 2 44 10 40 104 228
output:
140.8722825824867501548487425
result:
ok found '140.8722826', expected '140.8722826', error '0.0000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3892kb
input:
16 64 17 50 28 67 23 65 18 77 4 88 20 78 10 70 29 61 28 47 32 54 17 43 13 35 20 41 30 27 20 42 6 81 12 33 23
output:
64.2045377025227085657221870
result:
ok found '64.2045377', expected '64.2045377', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
16 64 17 50 28 67 23 65 18 77 4 88 20 78 10 70 29 61 28 47 32 54 17 43 13 35 20 41 30 27 20 42 6 33 23 81 12
output:
72.2834980411767275346179851
result:
ok found '72.2834980', expected '72.2834980', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
7 76 8 389 215 691 19 407 331 489 397 300 403 363 334 126 60 393 370
output:
6.6579177565105906165011940
result:
ok found '6.6579178', expected '6.6579178', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
3 0 1000 1000 0 1000 1000 567 578 589 601
output:
0.0000000000000015720538492
result:
ok found '0.0000000', expected '0.0000000', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
3 0 1000 0 0 1000 0 366 366 367 366
output:
0.0000000000000000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
5 50 93 278 178 199 300 596 362 208 519 421 388 142 153
output:
175.1697593917352965137146370
result:
ok found '175.1697594', expected '175.1697594', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
7 50 93 278 178 199 300 401 312 483 162 596 362 208 519 488 252 142 153
output:
289.6821398768899273878929534
result:
ok found '289.6821399', expected '289.6821399', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
8 10 10 40 25 20 25 20 35 12 23 30 23 10 20 5 40 15 15 19 26
output:
25.0000000000000000017347235
result:
ok found '25.0000000', expected '25.0000000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
9 5 1000 6 3 5 999 0 1000 0 0 500 2 500 0 1000 0 1000 1000 1 4 993 1
output:
5.1010479069859044898294087
result:
ok found '5.1010479', expected '5.1010479', error '0.0000000'
Test #13:
score: 0
Accepted
time: 29ms
memory: 4020kb
input:
100 695 43 538 87 463 208 597 329 750 306 812 481 960 555 912 344 983 450 987 573 994 852 941 985 801 855 792 800 849 806 792 696 924 701 939 672 710 546 722 668 723 807 715 767 624 524 634 554 547 503 357 352 627 458 651 495 937 558 932 545 864 509 753 489 509 397 341 335 300 495 199 528 380 688 48...
output:
1695.1865730236420720666856710
result:
ok found '1695.1865730', expected '1695.1865730', error '0.0000000'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3892kb
input:
20 840 854 839 45 996 905 959 938 852 938 730 423 425 493 136 481 213 778 527 740 691 941 22 830 83 313 462 155 636 21 462 321 360 324 238 422 402 492 806 406 952 822 410 838
output:
1424.3842014548487311387248155
result:
ok found '1424.3842015', expected '1424.3842015', error '0.0000000'
Test #15:
score: 0
Accepted
time: 23ms
memory: 3988kb
input:
74 89 395 52 622 124 832 115 698 95 598 199 491 190 356 191 398 132 315 94 371 34 221 91 0 153 139 220 465 260 283 312 30 409 15 338 50 343 52 437 69 359 89 332 213 377 505 375 396 405 199 657 90 658 50 360 50 618 23 642 7 824 191 688 417 795 227 709 286 662 321 646 175 485 210 381 357 420 329 441 3...
output:
2036.7557098766370524689506283
result:
ok found '2036.7557099', expected '2036.7557099', error '0.0000000'
Test #16:
score: 0
Accepted
time: 19ms
memory: 4012kb
input:
100 380 626 511 639 548 551 651 476 706 462 636 604 652 617 776 577 794 566 821 433 765 410 778 276 735 345 700 329 448 550 283 482 537 332 706 213 741 204 833 152 657 182 626 173 568 225 602 213 673 203 537 286 459 317 609 261 493 344 334 430 468 338 331 400 350 326 512 197 553 155 424 120 446 179 ...
output:
307.8507108572825656522820026
result:
ok found '307.8507109', expected '307.8507109', error '0.0000000'
Test #17:
score: 0
Accepted
time: 129ms
memory: 4116kb
input:
100 425 641 614 667 719 714 598 761 548 727 505 713 415 832 505 856 724 762 764 767 803 755 773 727 826 633 832 509 842 570 829 456 742 430 706 513 604 527 942 208 912 569 959 330 975 605 977 878 882 609 844 694 869 789 930 896 992 894 763 937 699 930 701 854 732 810 709 820 657 881 507 896 342 805 ...
output:
1941.5687357268885681049752634
result:
ok found '1941.5687357', expected '1941.5687357', error '0.0000000'
Test #18:
score: 0
Accepted
time: 110ms
memory: 4064kb
input:
100 845 528 842 889 837 997 809 663 786 746 793 554 782 470 769 798 709 992 520 993 95 983 191 897 250 666 136 715 139 745 32 979 32 918 5 916 0 740 31 283 10 238 36 177 102 740 141 635 145 353 132 435 106 607 130 383 41 66 139 12 403 11 330 45 225 48 153 216 251 342 233 374 289 424 266 99 334 62 34...
output:
1863.5717402634056304444598595
result:
ok found '1863.5717403', expected '1863.5717403', error '0.0000000'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
4 0 0 1000 0 1000 1000 0 1000 4 939 27 58
output:
0.0000000000000005354453806
result:
ok found '0.0000000', expected '0.0000000', error '0.0000000'
Test #20:
score: 0
Accepted
time: 3ms
memory: 3944kb
input:
94 5 5 995 5 995 995 5 995 990 990 5 990 970 970 5 970 950 950 5 950 930 930 5 930 910 910 5 910 890 890 5 890 870 870 5 870 850 850 5 850 830 830 5 830 810 810 5 810 790 790 5 790 770 770 5 770 750 750 5 750 730 730 5 730 710 710 5 710 690 690 5 690 670 670 5 670 650 650 5 650 630 630 5 630 610 610...
output:
620.2910607126302923175487081
result:
ok found '620.2910607', expected '620.2910607', error '0.0000000'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
8 0 0 20 0 20 30 60 30 60 0 80 0 80 50 0 50 70 30 70 10
output:
0.0000000000000000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
5 2 0 10 0 0 10 0 3 5 3 1 8 5 2
output:
5.0000000000000000000000000
result:
ok found '5.0000000', expected '5.0000000', error '0.0000000'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
5 2 0 10 0 0 10 0 3 5 3 1 4 5 2
output:
4.0000000000000000000000000
result:
ok found '4.0000000', expected '4.0000000', error '0.0000000'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3972kb
input:
12 0 0 2 0 2 4 1 4 1 5 2 5 2 7 0 7 0 3 1 3 1 2 0 2 1 6 1 1
output:
2.0000000000000000000000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
10 0 0 2 0 2 4 1 4 2 5 2 7 0 7 0 3 1 2 0 2 1 6 1 1
output:
2.0000000000000000000000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
12 0 0 2 0 3 3 5 0 6 3 7 0 8 2 7 6 5 2 4 6 2 2 0 2 1 1 7 1
output:
6.4787086646190748429226247
result:
ok found '6.4787087', expected '6.4787087', error '0.0000000'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
8 10 0 11 3 12 0 14 0 15 3 16 0 18 4 8 4 10 1 16 1
output:
5.8761229221400488333636181
result:
ok found '5.8761229', expected '5.8761229', error '0.0000000'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
8 10 0 11 3 12 0 16 3 14 0 17 0 17 4 8 4 10 1 15 1
output:
7.2360679774997896957638988
result:
ok found '7.2360680', expected '7.2360680', error '0.0000000'
Test #29:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
8 0 0 20 0 20 30 60 30 60 0 80 0 80 50 0 50 70 10 10 10
output:
58.1377674149945321210863902
result:
ok found '58.1377674', expected '58.1377674', error '0.0000000'
Test #30:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
11 0 0 4 0 4 1 5 1 5 0 7 0 7 2 3 2 3 1 2 2 0 2 6 1 1 1
output:
2.0000000000000000000000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
3 31 41 59 26 53 58 36 41 56 31
output:
0.0000000000000000543054346
result:
ok found '0.0000000', expected '0.0000000', error '0.0000000'
Test #32:
score: 0
Accepted
time: 10ms
memory: 3940kb
input:
97 6 10 8 10 8 12 6 12 6 14 4 8 2 6 2 10 4 10 2 12 4 12 4 14 0 14 0 0 4 0 4 2 2 2 2 4 4 4 4 6 6 6 6 8 8 4 8 2 6 4 6 0 8 0 10 2 10 0 16 0 12 2 16 2 18 0 22 0 12 4 22 4 22 6 24 6 24 2 18 2 24 0 26 2 26 6 22 8 14 10 32 10 24 8 26 8 28 6 28 2 26 0 30 0 32 2 36 4 36 2 34 2 32 0 38 0 38 6 30 2 32 4 30 4 3...
output:
72.4810350801867537204326020
result:
ok found '72.4810351', expected '72.4810351', error '0.0000000'
Test #33:
score: 0
Accepted
time: 38ms
memory: 4012kb
input:
97 180 20 190 20 170 30 160 30 160 40 170 40 180 30 190 30 190 40 180 40 170 50 160 50 160 60 170 60 180 50 190 50 180 60 190 60 190 70 150 60 100 50 110 50 110 30 100 30 100 40 90 40 90 30 80 40 80 30 70 20 70 30 50 30 60 40 70 40 50 60 80 60 70 50 90 50 90 60 140 60 180 70 60 70 30 60 50 70 20 70 ...
output:
240.4783856983092290571235594
result:
ok found '240.4783857', expected '240.4783857', error '0.0000000'
Test #34:
score: 0
Accepted
time: 18ms
memory: 4016kb
input:
89 10 15 10 10 5 10 5 15 0 15 0 0 5 0 5 5 15 5 10 0 100 0 20 5 25 5 15 10 85 10 30 5 90 5 105 0 285 0 295 5 350 5 290 0 445 0 355 5 380 5 450 0 735 0 715 5 665 5 710 10 730 10 720 5 735 5 740 0 745 0 740 5 745 5 745 15 740 10 735 10 740 15 685 15 705 10 630 10 660 5 590 5 610 10 625 10 680 15 615 15...
output:
306.4578983362806122725530145
result:
ok found '306.4578983', expected '306.4578983', error '0.0000000'
Test #35:
score: 0
Accepted
time: 10ms
memory: 3968kb
input:
94 5 5 995 5 995 995 5 995 990 990 5 990 970 970 5 970 950 950 5 950 930 930 5 930 910 910 5 910 890 890 5 890 870 870 5 870 850 850 5 850 830 830 5 830 810 810 5 810 790 790 5 790 770 770 5 770 750 750 5 750 730 730 5 730 710 710 5 710 690 690 5 690 670 670 5 670 650 650 5 650 630 630 5 630 610 610...
output:
1306.7333316327398173850582452
result:
ok found '1306.7333316', expected '1306.7333316', error '0.0000000'
Test #36:
score: 0
Accepted
time: 10ms
memory: 3928kb
input:
100 1000 20 1 40 1000 60 1 80 1000 100 1 120 1000 140 1 160 1000 180 1 200 1000 220 1 240 1000 260 1 280 1000 300 1 320 1000 340 1 360 1000 380 1 400 1000 420 1 440 1000 460 1 480 1000 500 1 520 1000 540 1 560 1000 580 1 600 1000 620 1 640 1000 660 1 680 1000 700 1 720 1000 740 1 760 1000 780 1 800 ...
output:
47913.5987375407170816288271453
result:
ok found '47913.5987375', expected '47913.5987375', error '0.0000000'
Test #37:
score: 0
Accepted
time: 89ms
memory: 4128kb
input:
100 0 0 1000 0 1000 1000 0 1000 0 3 998 2 998 998 2 998 2 5 996 4 996 996 4 996 4 7 994 6 994 994 6 994 6 9 992 8 992 992 8 992 8 11 990 10 990 990 10 990 10 13 988 12 988 988 12 988 12 15 986 14 986 986 14 986 14 17 984 16 984 984 16 984 16 19 982 18 982 982 18 982 18 21 980 20 980 980 20 980 20 23...
output:
46834.0056361912317512974368583
result:
ok found '46834.0056362', expected '46834.0056362', error '0.0000000'
Test #38:
score: 0
Accepted
time: 14ms
memory: 4124kb
input:
100 7 409 21 321 39 254 62 198 74 177 79 169 96 146 105 135 118 120 154 90 181 72 188 68 199 62 210 57 219 53 239 45 311 24 320 22 356 15 376 12 408 8 483 2 499 1 500 1 516 2 570 6 581 7 630 13 746 40 749 41 768 48 780 53 823 75 834 82 845 90 854 97 903 146 913 159 925 177 964 267 972 295 973 299 98...
output:
0.0000000000000365813537749
result:
ok found '0.0000000', expected '0.0000000', error '0.0000000'
Test #39:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
13 100 100 110 110 100 120 110 130 100 140 110 150 100 160 90 155 100 145 90 135 100 125 90 115 100 105 100 106 100 159
output:
34.0000000000000000000000000
result:
ok found '34.0000000', expected '34.0000000', error '0.0000000'
Test #40:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
13 100 100 110 90 120 100 130 90 140 100 150 90 160 100 155 110 145 100 135 110 125 100 115 110 105 100 106 100 159 100
output:
34.0000000000000000000000000
result:
ok found '34.0000000', expected '34.0000000', error '0.0000000'
Test #41:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
13 100 100 120 100 120 120 140 120 140 140 160 140 160 160 145 165 145 145 125 145 125 125 105 125 105 105 106 106 159 159
output:
48.0832611206852311505621778
result:
ok found '48.0832611', expected '48.0832611', error '0.0000000'
Test #42:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
13 100 100 100 120 80 120 80 140 60 140 60 160 40 160 35 145 55 145 55 125 75 125 75 105 95 105 94 106 41 159
output:
48.0832611206852315530180242
result:
ok found '48.0832611', expected '48.0832611', error '0.0000000'
Test #43:
score: 0
Accepted
time: 23ms
memory: 4092kb
input:
100 7 409 21 321 39 254 62 198 74 177 79 169 96 146 105 135 118 120 154 90 181 72 188 68 199 62 210 57 219 53 239 45 311 24 320 22 356 15 376 12 408 8 483 2 499 1 500 1 516 2 570 6 581 7 630 13 746 40 749 41 768 48 780 53 823 75 834 82 845 90 854 97 903 146 913 159 925 177 964 267 972 295 981 335 99...
output:
467.0010706625842456518604706
result:
ok found '467.0010707', expected '467.0010707', error '0.0000000'
Extra Test:
score: 0
Extra Test Passed