QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#393830#5612. Picking Up SteamJose_17AC ✓99ms21776kbC++2010.5kb2024-04-19 14:14:092024-04-19 14:14:10

Judging History

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

  • [2024-04-19 14:14:10]
  • 评测
  • 测评结果:AC
  • 用时:99ms
  • 内存:21776kb
  • [2024-04-19 14:14:09]
  • 提交

answer

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

// Holi c:

#define ll long long int
//#define ld long double
#define ii __int128
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()

const int Inf = 1e9;
const ll mod = 998244353;
const ll INF = 1e18;
const int maxn = 3e5 + 5;

using ld = long double;
const ld eps = 1e-9, inf = numeric_limits<ld>::max(), pi = acos(-1);
// For use with integers, just set eps=0 and everything remains the same
bool geq(ld a, ld b){return a-b >= -eps;}     //a >= b
bool leq(ld a, ld b){return b-a >= -eps;}     //a <= b
bool ge(ld a, ld b){return a-b > eps;}        //a > b
bool le(ld a, ld b){return b-a > eps;}        //a < b
bool eq(ld a, ld b){return abs(a-b) <= eps;}  //a == b
bool neq(ld a, ld b){return abs(a-b) > eps;}  //a != b

struct point{
	ld x, y;
	point(): x(0), y(0){}
	point(ld x, ld y): x(x), y(y){}

	point operator+(const point & p) const{return point(x + p.x, y + p.y);}
	point operator-(const point & p) const{return point(x - p.x, y - p.y);}
	point operator*(const ld & k) const{return point(x * k, y * k);}
	point operator/(const ld & k) const{return point(x / k, y / k);}

	point operator+=(const point & p){*this = *this + p; return *this;}
	point operator-=(const point & p){*this = *this - p; return *this;}
	point operator*=(const ld & p){*this = *this * p; return *this;}
	point operator/=(const ld & p){*this = *this / p; return *this;}

	point rotate(const ld & a) const{return point(x*cos(a) - y*sin(a), x*sin(a) + y*cos(a));}
	point perp() const{return point(-y, x);}
	ld ang() const{
		ld a = atan2l(y, x); a += le(a, 0) ? 2*pi : 0; return a;
	}
	ld dot(const point & p) const{return x * p.x + y * p.y;}
	ld cross(const point & p) const{return x * p.y - y * p.x;}
	ld norm() const{return x * x + y * y;}
	ld length() const{return sqrtl(x * x + y * y);}
	point unit() const{return (*this) / length();}

	bool operator==(const point & p) const{return eq(x, p.x) && eq(y, p.y);}
	bool operator!=(const point & p) const{return !(*this == p);}
	bool operator<(const point & p) const{return le(x, p.x) || (eq(x, p.x) && le(y, p.y));}
	bool operator>(const point & p) const{return ge(x, p.x) || (eq(x, p.x) && ge(y, p.y));}
	bool half(const point & p) const{return le(p.cross(*this), 0) || (eq(p.cross(*this), 0) && le(p.dot(*this), 0));}
};

istream &operator>>(istream &is, point & p){return is >> p.x >> p.y;}
ostream &operator<<(ostream &os, const point & p){return os << "(" << p.x << ", " << p.y << ")";}

int sgn(ld x){
	if(ge(x, 0)) return 1;
	if(le(x, 0)) return -1;
	return 0;
}

bool pointInLine(const point & a, const point & v, const point & p){
	//line a+tv, point p
	return eq((p - a).cross(v), 0);
}

bool pointInSegment(const point & a, const point & b, const point & p){
	//segment ab, point p
	return pointInLine(a, b - a, p) && leq((a - p).dot(b - p), 0);
}


point intersectLines(const point & a1, const point & v1, const point & a2, const point & v2){
	//lines a1+tv1, a2+tv2
	//assuming that they intersect
	ld det = v1.cross(v2);
	return a1 + v1 * ((a2 - a1).cross(v2) / det);
}

int intersectLinesInfo(const point & a1, const point & v1, const point & a2, const point & v2){
	//lines a1+tv1 and a2+tv2
	ld det = v1.cross(v2);
	if(eq(det, 0)){
		if(eq((a2 - a1).cross(v1), 0)){
			return -1; //infinity points
		}else{
			return 0; //no points
		}
	}else{
		return 1; //single point
	}
}

int intersectLineSegmentInfo(const point & a, const point & v, const point & c, const point & d){
	//line a+tv, segment cd
	point v2 = d - c;
	ld det = v.cross(v2);
	if(eq(det, 0)){
		if(eq((c - a).cross(v), 0)){
			return -1; //infinity points
		}else{
			return 0; //no point
		}
	}else{
		return sgn(v.cross(c - a)) != sgn(v.cross(d - a)); //1: single point, 0: no point
	}
}

int intersectSegmentsInfo(const point & a, const point & b, const point & c, const point & d){
	//segment ab, segment cd
	point v1 = b - a, v2 = d - c;
	int t = sgn(v1.cross(c - a)), u = sgn(v1.cross(d - a));
	if(t == u){
		if(t == 0){
			if(pointInSegment(a, b, c) || pointInSegment(a, b, d) || pointInSegment(c, d, a) || pointInSegment(c, d, b)){
				return -1; //infinity points
			}else{
				return 0; //no point
			}
		}else{
			return 0; //no point
		}
	}else{
		return sgn(v2.cross(a - c)) != sgn(v2.cross(b - c)); //1: single point, 0: no point
	}
}

ld f1(point c, ld r, point s0, point s1){
    point bi = s0 - s1; bi = bi.perp();
    auto at = intersectLines(c, bi, s0, s1 - s0);
    ld res = INF;
    if(at.x + eps >= min(s0.x, s1.x) && at.x - eps <= max(s0.x, s1.x)) res = min(res, (at - c).length());
    res = min(res, min((s0 - c).length(), (s1 - c).length()));
    if(res <= r + eps) return 0;
    return res - r;
}

ld f(point c, ld r0, point vt, point s0, point s1, ld in, ld fi){
    ld l = 0, r = Inf, ans = INF;
    for(int i = 0; i < 300; i++){
        ld m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
        ld g1 = f1(c + vt * m1, r0, s0, s1), g2 = f1(c + vt * m2, r0, s0, s1);
        if(!g1){
            ans = 0;
            r = m1; continue;
        }
        if(!g2){
            ans = 0;
            r = m2; continue;
        }
        if(g1 >= g2) l = m1;
        else r = m2;
    }
    //cout<<l<<" "<<f1(c + vt * l, r0, s0, s1)<<'\n';
    //if(f1(c + vt * l, r0, s0, s1) == 0) return l;
    point se = c + vt * l;
    point bi = s0 - s1; bi = bi.perp();
    auto at = intersectLines(se, bi, s0, s1 - s0);
    if(!(at.x + eps >= min(s0.x, s1.x) && at.x - eps <= max(s0.x, s1.x))){
        if((s0 - se).length() <= (s1 - se).length()) at = s0; else at = s1;
    }
    if(at.x - eps > fi || at.x + eps < in) return INF;
    if(!ans) return l;
    return INF;
}

int main(){
	ios_base::sync_with_stdio(false);  cin.tie(NULL); cout.tie(0);
	int n; cin>>n; vector<point> v(n + 1);
	for(int i = 0; i <= n; i++){
	    int a, b; cin>>a>>b; v[i] = point(a, b);
	}
	int cx, sx, sy, dx, dy, v1; ld r; cin>>cx>>sx>>sy>>r>>dx>>dy>>v1;
	point ini(sx, sy); point vt(dx, dy); vt = vt.unit() * v1; point cam;
	for(int i = 0; i < n; i++){
	    if(cx >= v[i].x && cx <= v[i + 1].x){
	        cam = intersectLines(v[i], v[i + 1] - v[i], point(cx, 0), point(cx, Inf) - point(cx, 0));
	        break;
	    }
	}
	int in = v[0].x, fi = v[n].x;
	cam.x = cx;
	//cout<<"Camara en: "<<cam<<" Punto inicial en: "<<ini<<" Con vector: "<<vt<<'\n';
	//cout<<"Poli-linea : "; for(auto e : v) cout<<e<<" "; cout<<'\n';
	vector<point> side1, side2, izq, der;
	int j1 = 0; //izq.pb(v[0]);
	while(v[j1].x < cam.x) izq.pb(v[j1++]);
	if(v[j1] == cam) j1++;
	while(j1 <= n) der.pb(v[j1++]);
	int m = izq.size(), k = der.size();
	//cout<<"Izq"<<'\n'; for(auto e : izq) cout<<e<<" "; cout<<'\n';
	//cout<<"Der"<<'\n'; for(auto e : der) cout<<e<<" "; cout<<'\n';
	//Reconstuir el poligono en dos partes segun quienes p0.x < cam.x || p0.x > cam.x
	//Introducir todos aquellos puntos (puntos limites de la poli-linea e intersecciones de la linea de vision con los segmentos) que se puedan ver desde cam
	//side1
	for(int i = 0; i < k; i++){
	    side1.pb(der[i]);
	    for(int j = 0; j < k - 1; j++){
	        if(intersectLineSegmentInfo(cam, der[i] - cam, der[j], der[j + 1]) == 1){
	            auto it = intersectLines(cam, der[i] - cam, der[j], der[j + 1] - der[j]);
	            if(it != der[i] && it != der[i + 1]) side1.pb(it);
	        }
	    }
	} //der.pb(der[der.size() - 1]);
	sort(all(side1));
	//side2
	for(int i = 0; i < m; i++){
	    side2.pb(izq[i]);
	    for(int j = 0; j < m - 1; j++){
	        if(intersectLineSegmentInfo(cam, izq[i] - cam, izq[j], izq[j + 1]) == 1){
	            auto it = intersectLines(cam, izq[i] - cam, izq[j], izq[j + 1] - izq[j]);
	            if(it != izq[j] && it != izq[j + 1]) side2.pb(it);
	        }
	    }
	} 
	sort(all(side2)); reverse(all(side2)); reverse(all(izq));
	//side1.erase(unique(all(side1)), side1.end()); side2.erase(unique(all(side2)), side2.end());
	//cout<<"Side1"<<'\n'; for(auto e : side1) cout<<e<<" "; cout<<'\n';
	//cout<<"Side2"<<'\n'; for(auto e : side2) cout<<e<<" "; cout<<'\n';
	//Limpiar los puntos, dado la anterior linea de vision mas proxima, verificar si se puede ver el punto
	vector<point> polyd, polyi;
	int j = 0, a = 1;
	for(int i = 0; i < side1.size(); i++){
	    if(j + a < k){
	        if(side1[i] == der[j + a]){
	            if((der[j] - cam).cross(side1[i] - cam) > eps) j += a, a = 1;
	            else a++;
	        } 
	    } 
	    if((der[j] - cam).cross(side1[i] - cam) >= -eps) polyd.pb(side1[i]);
	    //cout<<"Punto a analizar: "<<side1[i]<<" Con linea de vision en: "<<der[j]<<'\n';
	}
	j = 0; a = 1;
	for(int i = 0; i < side2.size(); i++){
	    if(j + a < m){
	        if(side2[i] == izq[j + a]){
	            if((izq[j] - cam).cross(side2[i] - cam) < -eps) j += a, a = 1;
	            else a++;
	        } 
	    } 
	    if((izq[j] - cam).cross(side2[i] - cam) <= eps) polyi.pb(side2[i]);
	}
	//Añadimos un punto final para representar el infinito
	if(polyd.size()) polyd.pb(cam + (polyd[polyd.size() - 1] - cam) * Inf);
	if(polyi.size()) polyi.pb(cam + (polyi[polyi.size() - 1] - cam) * Inf);
	//cout<<"Polyd"<<'\n'; for(auto e : polyd) cout<<e<<" "; cout<<'\n';
	//cout<<"Polyi"<<'\n'; for(auto e : polyi) cout<<e<<" "; cout<<'\n';
	//Verificar el tiempo que tarda la nube en cbocar con algun segmento del poliogno
	//Formula o ternaria
	ld ans = INF;
	for(int i = 0; i < polyd.size(); i++){
	    point p0, p1 = polyd[i];
	    if(i) p0 = polyd[i - 1]; else p0 = cam;
	    if(p0 == p1) continue;
	    if(abs((p0 - p1).cross(vt)) <= eps){
	        if(abs((p0 - ini).cross(p1 - ini)) <= eps) ans = min(ans, min((abs(p0.y - ini.y) - r) / vt.y, (abs(p1.y - ini.y) - r) / vt.y));
	    }else{
	        ans = min(ans, f(ini, r, vt, p0, p1, in, fi));
	    }
	}
	for(int i = 0; i < polyi.size(); i++){
	    point p0, p1 = polyi[i];
	    if(i) p0 = polyi[i - 1]; else p0 = cam;
	    if(p0 == p1) continue;
	    if(abs((p0 - p1).cross(vt)) <= eps){
	        if(abs((p0 - ini).cross(p1 - ini)) <= eps) ans = min(ans, min((abs(p0.y - ini.y) - r) / vt.y, (abs(p1.y - ini.y) - r) / vt.y));
	    }else{
	        ans = min(ans, f(ini, r, vt, p0, p1, in, fi));
	        //cout<<f(ini, r, vt, p0, p1, in, fi)<<" ";
	    }
	    //cout<<ans<<" ";
	}
	if(ans == INF) cout<<-1;
	else cout<<setprecision(25)<<ans;
}
// https://codeforces.com/gym/104614/problem/H
/*
11
1 10
2 6
4 5
5 3
6 2
9 2
12 3
13 3
15 5
16 8
17 8
18 6
7
7 -100
1
1 1
1

*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3924kb

input:

7 1 0 2 2 4 2 5 5 6 0 9 4 12 3 14 0
2 13 -1 1 -1 1 1

output:

8.89949493561166534057183

result:

ok found '8.89949', expected '8.89900', error '0.00006'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3924kb

input:

3 0 0 3 3 6 3 9 0
3 4 1 1 -1 1 1

output:

1.121320342559642573021517

result:

ok found '1.12132', expected '1.12132', error '0.00000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

3 0 0 3 3 6 3 9 0
4 4 1 1 -1 1 1

output:

1.414213560958881486209933

result:

ok found '1.41421', expected '1.41421', error '0.00000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 4096kb

input:

3 0 0 3 3 6 3 9 0
4 4 1 1 1 1 1

output:

1.414213560958881486209933

result:

ok found '1.41421', expected '1.41421', error '0.00000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 4088kb

input:

3 0 0 3 3 6 3 9 0
8 4 1 1 1 1 1

output:

1.828427123746190097511831

result:

ok found '1.82843', expected '1.82843', error '0.00000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3960kb

input:

3 0 0 3 3 6 3 9 0
0 4 1 1 0 1 1

output:

1.585786436212691388682357

result:

ok found '1.58579', expected '1.58579', error '0.00000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

3 0 0 3 3 6 3 9 0
0 4 1 1 1 1 1

output:

-1

result:

ok found '-1.00000', expected '-1.00000', error '-0.00000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

2 10 10 30 40 60 60
50 40 30 10 -1 1 1

output:

3.944096595525576927484743

result:

ok found '3.94410', expected '3.94410', error '0.00000'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

5 0 80 40 0 60 60 100 0 120 40 160 60
0 140 20 20 -1 1 1

output:

7.202420178618612872385035

result:

ok found '7.20242', expected '7.20242', error '0.00000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

5 0 80 40 0 60 60 100 0 120 40 160 60
0 140 20 20 0 1 1

output:

7.639320223884069042345063

result:

ok found '7.63932', expected '7.63932', error '0.00000'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3992kb

input:

3 -4 4 -1 3 0 0 3 3
-4 2 0 1 -1 1 1

output:

2.006572707383427471745929

result:

ok found '2.00657', expected '2.00657', error '0.00000'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3992kb

input:

9 -12 5 -10 2 -8 7 -6 5 -5 2 -3 2 -2 3 -1 6 1 6 3 4
0 -8 3 1 1 1 1

output:

2.828427123331976534865301

result:

ok found '2.82843', expected '2.82843', error '0.00000'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3876kb

input:

9 -12 5 -10 2 -8 7 -6 5 -5 2 -3 2 -2 3 -1 6 1 6 3 4
-12 -8 3 1 1 1 1

output:

8.151430835654103396192838

result:

ok found '8.15143', expected '8.15143', error '0.00000'

Test #14:

score: 0
Accepted
time: 1ms
memory: 3996kb

input:

8 -4956 0 -413 0 413 1239 1239 0 1652 826 2478 826 3404 1239 3717 1239 5000 0
413 -1239 -1652 413 2 1 1

output:

2770.488224120003365680276

result:

ok found '2770.48822', expected '2770.48822', error '0.00000'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3960kb

input:

2 0 3 3 0 6 3
1 3 -1 1 0 1 1

output:

0

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3964kb

input:

20 1 11 4 1 5 14 6 8 8 8 9 1 12 14 14 12 17 8 21 6 25 1 27 8 29 4 35 5 37 16 38 17 39 16 45 9 47 4 48 11 49 2
6 21 -2 1 0 15 5

output:

4.717157287242538277281106

result:

ok found '4.71716', expected '4.71716', error '0.00000'

Test #17:

score: 0
Accepted
time: 1ms
memory: 4000kb

input:

20 2 10 4 4 6 13 9 3 10 12 11 5 12 0 14 15 15 10 17 20 19 8 21 4 28 18 29 7 32 10 36 2 39 0 40 5 41 6 42 18 47 2
33 34 -11 4 -3 13 1

output:

15.35383113412920330718286

result:

ok found '15.35383', expected '15.35383', error '0.00000'

Test #18:

score: 0
Accepted
time: 1ms
memory: 3888kb

input:

33 -4858 1505 -4750 252 -4377 2301 -4299 1512 -4124 4848 -3928 551 -3650 1782 -3242 163 -3241 4713 -2817 1286 -2753 2708 -1859 4013 -991 2481 -837 2253 356 669 385 4947 558 336 841 4286 1041 91 1122 3030 1371 4183 1456 1266 1632 844 1802 4762 2340 4087 2353 2421 2696 1915 3294 220 4405 3012 4413 481...

output:

43.6180615051982695992705

result:

ok found '43.61806', expected '43.61806', error '0.00000'

Test #19:

score: 0
Accepted
time: 1ms
memory: 3820kb

input:

20 0 11 4 18 5 0 9 5 10 17 12 2 13 0 16 11 18 3 19 5 21 3 25 19 31 2 32 6 34 13 35 9 37 20 42 0 45 12 46 14 47 4
38 9 -15 5 -1 15 3

output:

57.57500676401814981852922

result:

ok found '57.57501', expected '57.57501', error '0.00000'

Test #20:

score: 0
Accepted
time: 1ms
memory: 3808kb

input:

20 0 7 1 8 5 18 10 10 12 7 13 8 15 0 16 1 17 7 19 11 25 13 26 2 27 2 29 4 37 14 38 6 40 12 42 17 43 15 44 6 47 3
41 4 -14 1 6 5 5

output:

8.368394940890755382377486

result:

ok found '8.36839', expected '8.36839', error '0.00000'

Test #21:

score: 0
Accepted
time: 1ms
memory: 3868kb

input:

15 -4759 2812 -4596 3951 -4052 4157 -3244 779 -2591 4780 -1380 81 -839 3638 -757 1156 8 392 881 3169 1035 2070 1390 3818 1982 3218 2020 2830 2686 2080 3928 4241
1390 1388 -1229 398 439 4605 41

output:

100.1453774504183090732212

result:

ok found '100.14538', expected '100.14538', error '0.00000'

Test #22:

score: 0
Accepted
time: 3ms
memory: 4092kb

input:

100 2 144 10 36 12 238 14 286 17 461 19 257 20 174 25 6 32 96 38 199 52 451 59 304 61 372 64 17 65 426 70 432 76 40 77 253 79 382 82 164 84 408 94 208 99 386 102 434 103 482 104 428 111 95 112 192 114 381 117 285 124 259 130 289 131 402 133 462 136 10 138 367 147 500 150 365 153 145 156 267 157 299 ...

output:

34.4888004591927199195267

result:

ok found '34.48880', expected '34.48880', error '0.00000'

Test #23:

score: 0
Accepted
time: 3ms
memory: 3880kb

input:

100 13 43 14 384 16 276 22 343 26 375 28 453 29 369 40 265 41 153 45 81 51 446 58 58 62 388 65 187 73 109 77 167 79 59 98 316 104 257 105 133 112 68 120 345 133 95 144 290 145 70 146 375 152 118 160 362 166 75 167 479 168 48 176 141 178 45 181 339 183 355 184 261 188 221 189 267 196 108 207 263 211 ...

output:

-1

result:

ok found '-1.00000', expected '-1.00000', error '-0.00000'

Test #24:

score: 0
Accepted
time: 3ms
memory: 3984kb

input:

100 2 193 6 307 13 193 21 160 26 80 29 116 30 136 35 398 40 228 41 161 59 180 61 120 64 310 65 285 69 268 73 261 74 79 78 30 84 135 85 85 94 485 98 195 105 143 108 50 114 129 120 30 131 247 139 223 143 147 144 431 148 1 150 452 151 443 163 461 164 25 168 210 173 339 174 41 175 224 179 211 189 112 19...

output:

92.5301107888059161041272

result:

ok found '92.53011', expected '92.53011', error '0.00000'

Test #25:

score: 0
Accepted
time: 2ms
memory: 3984kb

input:

100 4 309 20 470 23 362 29 439 30 342 46 465 49 363 55 6 56 40 58 478 61 358 62 459 64 326 71 135 73 499 75 490 83 241 86 429 93 44 98 349 100 415 104 13 106 341 120 19 128 467 130 175 131 235 137 58 138 101 155 205 156 19 157 364 159 124 163 222 168 255 174 207 177 87 181 240 186 224 188 119 194 47...

output:

16.98622929160100156892321

result:

ok found '16.98623', expected '16.98623', error '0.00000'

Test #26:

score: 0
Accepted
time: 3ms
memory: 3924kb

input:

171 -4951 4053 -4885 4474 -4850 3308 -4820 2830 -4798 2464 -4783 4657 -4759 1857 -4599 890 -4467 1174 -4461 1849 -4352 1814 -4261 1358 -4191 4986 -4149 2579 -4004 891 -3988 4057 -3944 4843 -3886 4375 -3710 818 -3644 877 -3546 4297 -3510 4384 -3331 4080 -3286 3168 -3271 940 -3267 3829 -3206 161 -3172...

output:

-1

result:

ok found '-1.00000', expected '-1.00000', error '-0.00000'

Test #27:

score: 0
Accepted
time: 16ms
memory: 5532kb

input:

439 -4990 2843 -4970 4753 -4935 1802 -4918 2606 -4900 2888 -4886 3403 -4870 1607 -4826 3029 -4813 2183 -4742 3075 -4712 3708 -4701 1752 -4599 3587 -4583 2542 -4537 134 -4529 1165 -4515 54 -4506 2457 -4489 661 -4478 2497 -4456 503 -4443 3259 -4376 3839 -4368 745 -4353 1067 -4345 939 -4299 4447 -4274 ...

output:

1.010635909064978424040139

result:

ok found '1.01064', expected '1.01064', error '0.00000'

Test #28:

score: 0
Accepted
time: 6ms
memory: 4032kb

input:

199 -5000 1106 -4984 2688 -4978 1052 -4891 3232 -4885 3569 -4845 3316 -4769 2665 -4761 3787 -4715 4499 -4695 3669 -4684 504 -4663 301 -4653 2757 -4643 4988 -4636 659 -4497 2931 -4423 4876 -4384 4305 -4375 4182 -4369 1732 -4233 1650 -4134 1345 -4131 3428 -4116 1789 -4109 3889 -4103 802 -4065 562 -389...

output:

7420.582836671282266571836

result:

ok found '7420.58284', expected '7420.58284', error '0.00000'

Test #29:

score: 0
Accepted
time: 14ms
memory: 4448kb

input:

329 -4967 2068 -4948 502 -4817 126 -4790 3333 -4762 571 -4717 347 -4679 617 -4677 750 -4660 3188 -4629 3658 -4621 3788 -4599 3306 -4441 3746 -4397 3152 -4300 2648 -4293 111 -4291 1800 -4286 1336 -4262 4102 -4256 378 -4189 4296 -4185 4939 -4184 171 -4168 603 -4164 3289 -4100 3971 -4061 2049 -4008 295...

output:

-1

result:

ok found '-1.00000', expected '-1.00000', error '-0.00000'

Test #30:

score: 0
Accepted
time: 27ms
memory: 9060kb

input:

602 -4981 4519 -4948 4604 -4919 4617 -4900 1297 -4896 2508 -4889 4316 -4862 2086 -4851 2284 -4800 3614 -4799 3395 -4767 258 -4750 4182 -4749 545 -4720 652 -4709 1101 -4702 2728 -4691 2729 -4690 674 -4687 194 -4608 2131 -4592 3030 -4584 2898 -4549 1033 -4533 3912 -4525 1943 -4508 1369 -4451 972 -4432...

output:

74.89721745721776383769575

result:

ok found '74.89722', expected '74.89722', error '0.00000'

Test #31:

score: 0
Accepted
time: 2ms
memory: 3984kb

input:

208 -4929 2891 -4849 901 -4801 901 -4795 3319 -4662 2937 -4655 3294 -4606 4566 -4605 1114 -4583 3792 -4536 2579 -4506 1770 -4332 4485 -4327 2658 -4296 979 -4289 3652 -4245 1384 -4111 4184 -4110 3675 -4016 4437 -3990 4623 -3958 1514 -3921 2233 -3820 2119 -3757 692 -3739 1616 -3735 4228 -3723 4366 -36...

output:

152.9758283871132591158482

result:

ok found '152.97583', expected '152.97583', error '0.00000'

Test #32:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

2 -5000 0 0 5000 5000 0
0 0 -5000 5000 0 5000 1000

output:

2.928932188133110542382909

result:

ok found '2.92893', expected '2.92893', error '0.00000'

Test #33:

score: 0
Accepted
time: 0ms
memory: 3920kb

input:

2 -5000 0 0 5000 5000 0
0 0 -5000 5000 -5000 1 1000

output:

4.900999901930002918600676

result:

ok found '4.90100', expected '4.90100', error '0.00000'

Test #34:

score: 0
Accepted
time: 67ms
memory: 20608kb

input:

1000 -5000 5000 -4990 10 -4980 4990 -4970 20 -4960 4980 -4950 30 -4940 4970 -4930 40 -4920 4960 -4910 50 -4900 4950 -4890 60 -4880 4940 -4870 70 -4860 4930 -4850 80 -4840 4920 -4830 90 -4820 4910 -4810 100 -4800 4900 -4790 110 -4780 4890 -4770 120 -4760 4880 -4750 130 -4740 4870 -4730 140 -4720 4860...

output:

1988028.995984449836441854

result:

ok found '1988028.99598', expected '1988028.99598', error '0.00000'

Test #35:

score: 0
Accepted
time: 99ms
memory: 21776kb

input:

1000 -5000 5000 -4990 10 -4980 4990 -4970 20 -4960 4980 -4950 30 -4940 4970 -4930 40 -4920 4960 -4910 50 -4900 4950 -4890 60 -4880 4940 -4870 70 -4860 4930 -4850 80 -4840 4920 -4830 90 -4820 4910 -4810 100 -4800 4900 -4790 110 -4780 4890 -4770 120 -4760 4880 -4750 130 -4740 4870 -4730 140 -4720 4860...

output:

2495.392220792512627092208

result:

ok found '2495.39222', expected '2495.39222', error '0.00000'

Test #36:

score: 0
Accepted
time: 40ms
memory: 11240kb

input:

1000 -5000 5000 -4990 10 -4980 4990 -4970 20 -4960 4980 -4950 30 -4940 4970 -4930 40 -4920 4960 -4910 50 -4900 4950 -4890 60 -4880 4940 -4870 70 -4860 4930 -4850 80 -4840 4920 -4830 90 -4820 4910 -4810 100 -4800 4900 -4790 110 -4780 4890 -4770 120 -4760 4880 -4750 130 -4740 4870 -4730 140 -4720 4860...

output:

2499.99999999899999991726

result:

ok found '2500.00000', expected '2500.00000', error '0.00000'

Test #37:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

2 -5000 0 0 5000 5000 0
0 -4999 -2 1 -1 1 1

output:

1.414213560958881486860454

result:

ok found '1.41421', expected '1.41421', error '0.00000'

Test #38:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

2 -5000 0 0 5000 5000 0
0 4999 -2 1 1 1 1

output:

1.414213560958881486860454

result:

ok found '1.41421', expected '1.41421', error '0.00000'

Test #39:

score: 0
Accepted
time: 0ms
memory: 3920kb

input:

2 -5000 0 -4999 5000 -4998 0
-4999 -4999 -2 1 -1 1 1

output:

1.414213560958881486860454

result:

ok found '1.41421', expected '1.41421', error '0.00000'

Test #40:

score: 0
Accepted
time: 0ms
memory: 4024kb

input:

2 -5000 0 -4999 5000 -4998 0
-4999 -4999 -2 1 1 1 1

output:

1.414213560958881486860454

result:

ok found '1.41421', expected '1.41421', error '0.00000'

Test #41:

score: 0
Accepted
time: 0ms
memory: 3988kb

input:

2 -5000 0 0 1 5000 0
-2500 0 -5000 5000 0 1 1000

output:

0.000999899999000999573034439

result:

ok found '0.00100', expected '0.00100', error '0.00000'

Test #42:

score: 0
Accepted
time: 0ms
memory: 4024kb

input:

2 -5000 4999 0 5000 5000 4999
2500 0 -5000 1 0 1 1

output:

9998.999999979000000038809

result:

ok found '9999.00000', expected '9999.00000', error '0.00000'

Test #43:

score: 0
Accepted
time: 26ms
memory: 9364kb

input:

500 -5000 0 -4980 5000 -4960 20 -4940 4980 -4920 40 -4900 4960 -4880 60 -4860 4940 -4840 80 -4820 4920 -4800 100 -4780 4900 -4760 120 -4740 4880 -4720 140 -4700 4860 -4680 160 -4660 4840 -4640 180 -4620 4820 -4600 200 -4580 4800 -4560 220 -4540 4780 -4520 240 -4500 4760 -4480 260 -4460 4740 -4440 28...

output:

3535.811256034591734342953

result:

ok found '3535.81126', expected '3535.81126', error '0.00000'

Test #44:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

21 0 0 1 2 2 1 3 4 4 1 5 5 6 4 7 9 11 8 14 7 16 6 17 5 18 3 21 4 23 5 24 6 25 8 26 9 28 9 29 10 32 10 33 11
0 10 1 4 43 11 79

output:

-1

result:

ok found '-1.00000', expected '-1.00000', error '-0.00000'

Test #45:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

21 0 0 1 2 2 1 3 4 4 1 5 5 6 4 7 9 11 8 14 7 16 6 17 5 18 3 21 4 23 5 24 6 25 8 26 9 28 9 29 10 32 10 33 11
0 10 1 4 -43 11 79

output:

0.05824354611506071406601924

result:

ok found '0.05824', expected '0.05824', error '0.00000'

Test #46:

score: 0
Accepted
time: 1ms
memory: 4092kb

input:

21 0 0 1 2 2 1 3 4 4 1 5 5 6 4 7 9 11 8 14 7 16 6 17 5 18 3 21 4 23 5 24 6 25 8 26 9 28 9 29 10 32 10 33 11
8 10 1 4 43 11 79

output:

0.08077183910444029263576331

result:

ok found '0.08077', expected '0.08077', error '0.00000'

Test #47:

score: 0
Accepted
time: 1ms
memory: 3868kb

input:

21 0 0 1 2 2 1 3 4 4 1 5 5 6 4 7 9 11 8 14 7 16 6 17 5 18 3 21 4 23 5 24 6 25 8 26 9 28 9 29 10 32 10 33 11
8 10 1 4 -43 11 79

output:

-1

result:

ok found '-1.00000', expected '-1.00000', error '-0.00000'

Test #48:

score: 0
Accepted
time: 1ms
memory: 3856kb

input:

21 0 0 1 2 2 1 3 4 4 1 5 5 6 4 7 9 11 8 14 7 16 6 17 5 18 3 21 4 23 5 24 6 25 8 26 9 28 9 29 10 32 10 33 11
11 10 1 4 43 11 79

output:

0.0691266240650382714796841

result:

ok found '0.06913', expected '0.06913', error '0.00000'

Test #49:

score: 0
Accepted
time: 1ms
memory: 3928kb

input:

21 0 0 1 2 2 1 3 4 4 1 5 5 6 4 7 9 11 8 14 7 16 6 17 5 18 3 21 4 23 5 24 6 25 8 26 9 28 9 29 10 32 10 33 11
18 10 1 4 -11 43 79

output:

0.2422758359477793600403198

result:

ok found '0.24228', expected '0.24228', error '0.00000'

Test #50:

score: 0
Accepted
time: 1ms
memory: 3812kb

input:

21 0 0 1 2 2 1 3 4 4 1 5 5 6 4 7 9 11 8 14 7 16 6 17 5 18 3 21 4 23 5 24 6 25 8 26 9 28 9 29 10 32 10 33 11
33 10 1 4 -11 43 79

output:

0.04364689442289630719016983

result:

ok found '0.04365', expected '0.04365', error '0.00000'

Test #51:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

2 -5000 1 -4999 0 4999 2
-5000 -4999 -1 1 4999 1 1

output:

0

result:

ok found '0.00000', expected '0.00000', error '-0.00000'

Test #52:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

2 -5000 0 -4999 5000 5000 0
-5000 5000 -1 1 0 5000 1

output:

49995000.99989499999719555

result:

ok found '49995000.99989', expected '49999999.00000', error '0.00010'

Test #53:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

2 -5000 0 4999 5000 5000 0
5000 -5000 -1 1 0 1 1

output:

49995000.99989499999719555

result:

ok found '49995000.99989', expected '49999999.00000', error '0.00010'