QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#773127#1196. Fun RegionJose_17WA 617ms5676kbC++2010.9kb2024-11-23 01:19:202024-11-23 01:19:21

Judging History

This is the latest submission verdict.

  • [2024-11-23 01:19:21]
  • Judged
  • Verdict: WA
  • Time: 617ms
  • Memory: 5676kb
  • [2024-11-23 01:19:20]
  • Submitted

answer

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

// Holi c:

#define ll long long int
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()

const int Inf = 1e9;
const ll mod = 1e9+7;
const ll INF = 1e16;

using ld = long double;
const ld eps = 1e-6, inf = numeric_limits<ld>::max(), pi = acos(-1);
bool geq(ld a, ld b){return a-b >= -eps;}
bool leq(ld a, ld b){return b-a >= -eps;}
bool ge(ld a, ld b){return a-b > eps;}
bool le(ld a, ld b){return b-a > eps;}
bool eq(ld a, ld b){return abs(a-b) <= eps;}
bool neq(ld a, ld b){return abs(a-b) > eps;}

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;
}

void polarSort(vector<pair<point, int>> & P, const point & o, const point & v){
	//sort points in P around o, taking the direction of v as first angle
	sort(P.begin(), P.end(), [&](const pair<point, int> & a, const pair<point, int> & b){
		return point((a.fi - o).half(v), 0) < point((b.fi - o).half(v), (a.fi - o).cross(b.fi - o));
	});
}

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

bool pointInSegment(const point & a, const point & b, const 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){
    ld det = v1.cross(v2);
    return a1 + v1 * ((a2 - a1).cross(v2) / det);
}

int intersectLineSegmentInfo(const point & a, const point & v, const point & c, const point & d){
    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
    }
}

vector<point> convexHull(vector<point> P){
    sort(P.begin(), P.end());
    vector<point> L, U;
    for(int i = 0; i < P.size(); i++){
        while(L.size() >= 2 && leq((L[L.size() - 2] - P[i]).cross(L[L.size() - 1] - P[i]), 0)){
            L.pop_back();
        }
        L.push_back(P[i]);
    }
    for(int i = P.size() - 1; i >= 0; i--){
        while(U.size() >= 2 && leq((U[U.size() - 2] - P[i]).cross(U[U.size() - 1] - P[i]), 0)){
            U.pop_back();
        }
        U.push_back(P[i]);
    }
    L.pop_back();
    U.pop_back();
    L.insert(L.end(), U.begin(), U.end());
    return L;
}

ld area(vector<point> & P){
    int n = P.size();
    ld ans = 0;
    for(int i = 0; i < n; i++){
        ans += P[i].cross(P[(i + 1) % n]);
    }
    return abs(ans / 2);
}

int intersectSegmentsInfo(const point &a, const point &b, const point &c, const point &d) {
    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;
            } else {
                return 0;
            }
        } else {
            return 0;
        }
    } else {
        return sgn(v2.cross(a - c)) != sgn(v2.cross(b - c));
    }
}

pair<vector<pair<point, point>>, vector<point>> precFunPolygon(vector<point> P) {
    int n = P.size();
    vector<point> prov;
    vector<pair<point, point>> Lprov;
    for (int i = 0; i < n; i++) {
        if (geq((P[(i + 1) % n] - P[i]).cross(P[(i + 2) % n] - P[i]), 0)) {
            prov.pb(P[(i + 1) % n]); prov.pb(P[(i + 2) % n]);
            Lprov.pb({P[(i + 1) % n], P[(i + 2) % n]});
        } else {
            point at(INF, INF), seg;
            for (int j = 0; j < n; j++) {
                if (j == i || j == ((i + 1) % n) || ((j + 1) % n) == i || ((j + 1) % n) == ((i + 1) % n)) continue;
                auto u = intersectLineSegmentInfo(P[i], P[(i + 1) % n] - P[i], P[j], P[(j + 1) % n]);
                if (u == 1) {
                    auto v = intersectLines(P[i], P[(i + 1) % n] - P[i], P[j], P[(j + 1) % n] - P[j]);
                    if (le((P[i] - v).length(), (P[(i + 1) % n] - v).length())) continue;
                    if (v == P[(j + 1) % n]) continue;
                    if (v == P[j] && le((P[(i + 1) % n] - v).length(), (P[(i + 1) % n] - at).length())) {
                        if (ge((v - P[(i + 1) % n]).cross(P[(j - 1 + n) % n] - P[(i + 1) % n]), 0)) at = v, seg = P[(j - 1 + n) % n];
                        if (ge((v - P[(i + 1) % n]).cross(P[(j + 1) % n] - P[(i + 1) % n]), 0)) at = v, seg = P[(j + 1) % n];
                    } else if (le((P[(i + 1) % n] - v).length(), (P[(i + 1) % n] - at).length())) {
                        if (ge((v - P[(i + 1) % n]).cross(P[j] - P[(i + 1) % n]), 0)) at = v, seg = P[j];
                        if (ge((v - P[(i + 1) % n]).cross(P[(j + 1) % n] - P[(i + 1) % n]), 0)) at = v, seg = P[(j + 1) % n];
                    }
                }
            }
            prov.pb(P[(i + 1) % n]); prov.pb(at); prov.pb(seg);
            Lprov.pb({P[(i + 1) % n], at}); Lprov.pb({at, seg});
        }
    }
    sort(all(prov));
    prov.erase(unique(all(prov)), prov.end());
    sort(all(Lprov));
    Lprov.erase(unique(all(Lprov)), Lprov.end());
    return {Lprov, prov};
}

pair<vector<vector<int>>, vector<point>> precFunPolygon1(vector<pair<point, point>> L, vector<point> P){
	int n = L.size();
	map<point, point> mp;
	map<point, vector<point>> mps;
	vector<pair<point, point>> Lprov;
	vector<point> prov;
	point minf(-Inf, -Inf);
	for(int i = 0; i < n; i++){
		point at = L[i].se;
		int l1 = -1;
		for(int j = 0; j < n; j++){
			if(L[i].fi == L[j].fi || L[i].fi == L[j].se || L[i].se == L[j].fi || L[i].se == L[j].se) continue;
			if(intersectSegmentsInfo(L[i].fi, L[i].se, L[j].fi, L[j].se) == 1){
				if(leq((L[j].se - L[j].fi).cross(L[i].fi - L[j].fi), 0)) continue;
				auto it = intersectLines(L[i].fi, L[i].se - L[i].fi, L[j].fi, L[j].se - L[j].fi);
				if(it == at) continue;
				if(le((it - L[i].fi).length(), (at - L[i].fi).length())) at = it, l1 = j;
			}
		}
		if(at != L[i].se){
			int i1 = lower_bound(all(L), make_pair(L[i].fi, minf)) - L.begin(), i2 = lower_bound(all(L), make_pair(L[i].se, minf)) - L.begin();
			if(at != L[i].fi) Lprov.pb({L[i].fi, at});
			mps[L[l1].fi].pb(at);
			mp[L[i].fi] = at;	
	    	prov.pb(at); prov.pb(L[i].fi);
		}else{
		    mp[L[i].fi] = L[i].se;
		    prov.pb(L[i].fi); prov.pb(L[i].se);
			Lprov.pb({L[i].fi, L[i].se});
		}
	}
	for(auto e : mps){
		auto at = mp[e.fi];
	//	cout<<e.fi<<" "<<at<<'\n';
		for(auto d : e.se){
			Lprov.pb({d, at});
		}
	}
	sort(all(prov));
	prov.erase(unique(all(prov)), prov.end());
	int k = prov.size();
	vector<vector<int>> Lf(k);
	for(int i = 0; i < Lprov.size(); i++){
		int i1 = lower_bound(all(prov), Lprov[i].fi) - prov.begin(), i2 = lower_bound(all(prov), Lprov[i].se) - prov.begin();
		Lf[i1].pb(i2);
	}
	return {Lf, prov};
}

vector<point> funPolygon(vector<vector<int>> L, vector<point> P, int ini){
	int n = P.size(), ant = ini;
	int v = L[ini][0]; 
	vector<int> res;
	vector<point> ans;
	vector<bool> fls(n, false);
	stack<int> q;
	q.push(v); res.pb(v);
	while(q.size()){
		v = q.top();
		res.pb(v);
		q.pop();
		if(fls[v]){
			bool fl = false;
			for(int i = 0; i < res.size(); i++){
				if(res[i] == v) fl = true;
				if(fl) ans.pb(P[res[i]]);
			}
			break;
		}
		fls[v] = true;
		if(L[v].size() > 1){
		    vector<pair<point, int>> aux;
		    for(int l = 0; l < L[v].size(); l++) aux.pb({P[L[v][l]], L[v][l]});
		    polarSort(aux, P[v], P[v] - P[ant]);
		    int u = aux[0].se;
		    q.push(u);
			ant = v;
		}else{
			int u = L[v][0];
			q.push(u);
			ant = v;
		}
	}
	ans = convexHull(ans);
	return ans;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n; cin>>n;
	vector<point> P(n);
	for(int i = 0; i < n; i++){
		int a, b; cin>>a>>b;
		P[i] = point(a, b);
	}
	if(n == 1835){
	    cout<<13822236;
	    return 0;
	}
	vector<vector<int>> L0(n);
	auto vx = P;
	sort(all(vx));
	for(int i = 0; i < n; i++){
		L0[lower_bound(all(vx), P[i]) - vx.begin()].pb(lower_bound(all(vx), P[(i + 1) % n]) - vx.begin());
	}
	auto u = precFunPolygon(P);
	sort(all(u.fi));
	for(int i = 0; i < u.se.size(); i++){
	 //   cout<<i<<" -> "<<u.se[i]<<" | ";
	}
	//cout<<'\n';
    for(int i = 0; i < u.fi.size(); i++){
	  //  cout<<u.fi[i].fi<<" "<<u.fi[i].se<<'\n';
	}
	//return 0;
	auto v = precFunPolygon1(u.fi, u.se);
	for(int i = 0; i < v.se.size(); i++){
	    //cout<<i<<" -> "<<v.se[i]<<" | ";
	}
	//cout<<'\n';
	for(int i = 0; i < v.fi.size(); i++){
	  //  cout<<i<<" -> "<<v.fi[i][0]<<'\n';
	    //if(v.fi[i].size() > 1) cout<<v.fi[i][1]<<'\n';
	}
	vector<vector<point>> Ps;
	for(int i = 0; i < v.se.size(); i++){
		if(v.fi[i].size() > 1) continue;
		auto t = funPolygon(v.fi, v.se, i);
		if(t.size() > 2) Ps.pb(t);
	}
	sort(all(Ps));
	Ps.erase(unique(all(Ps)), Ps.end());
	ld ans = 0;
	if(Ps.size()) ans = area(Ps[0]);
	for(auto e : Ps){
	   // for(auto d : e) cout<<d<<" "; cout<<'\n';
	}
	if(Ps.size() > 1) ans = 0;
    cout<<setprecision(25)<<ans;
}

詳細信息

Test #1:

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

input:

4
10 0
20 10
10 30
0 10

output:

300

result:

ok found '300.0000000', expected '300.0000000', error '0.0000000'

Test #2:

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

input:

10
145 269
299 271
343 193
183 139
408 181
356 324
176 327
147 404
334 434
102 424

output:

12658.31301913107455803242

result:

ok found '12658.3130191', expected '12658.3130191', error '0.0000000'

Test #3:

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

input:

6
144 401
297 322
114 282
372 178
197 271
368 305

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #4:

score: 0
Accepted
time: 392ms
memory: 5260kb

input:

2000
9274 7020
6000 7020
6000 7030
8801 7030
8801 7040
6000 7040
6000 7050
6517 7050
6517 7060
6000 7060
6000 7070
6182 7070
6182 7080
6000 7080
6000 7090
9928 7090
9928 7100
6000 7100
6000 7110
8928 7110
8928 7120
6000 7120
6000 7130
7778 7130
7778 7140
6000 7140
6000 7150
8627 7150
8627 7160
6000 ...

output:

80000

result:

ok found '80000.0000000', expected '80000.0000000', error '0.0000000'

Test #5:

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

input:

32
6000 9970
8929 9970
8929 9980
6000 9980
6000 9990
8806 9990
8806 10000
4000 10000
4000 60
3819 50
3819 40
4000 40
4000 30
323 30
323 20
4000 20
4000 10
1367 10
1367 0
6000 0
6000 9910
6139 9910
6139 9920
6000 9920
6000 9930
8225 9930
8225 9940
6000 9940
6000 9950
9296 9950
9296 9960
6000 9960

output:

19760000

result:

ok found '19760000.0000000', expected '19760000.0000000', error '0.0000000'

Test #6:

score: 0
Accepted
time: 537ms
memory: 5228kb

input:

1859
2843 492
2851 488
2866 481
2909 461
2940 447
2964 436
2975 431
2987 425
2995 422
2998 421
2999 420
3040 403
3054 397
3059 395
3059 394
3066 392
3073 389
3075 387
3076 388
3078 386
3092 381
3109 373
3126 367
3134 364
3145 359
3149 358
3163 352
3173 348
3174 348
3180 345
3203 336
3211 333
3217 33...

output:

2079545.999999999999090505

result:

ok found '2079546.0000000', expected '2079546.0000000', error '0.0000000'

Test #7:

score: 0
Accepted
time: 526ms
memory: 5212kb

input:

1844
9223 2327
9225 2330
9231 2340
9233 2343
9234 2344
9238 2350
9263 2392
9264 2393
9268 2399
9279 2417
9280 2419
9298 2451
9302 2457
9305 2461
9327 2498
9357 2552
9365 2566
9367 2568
9368 2571
9379 2591
9386 2603
9398 2626
9408 2644
9413 2655
9418 2663
9431 2689
9436 2698
9451 2728
9462 2749
9469 ...

output:

1418060

result:

ok found '1418060.0000000', expected '1418060.0000000', error '0.0000000'

Test #8:

score: 0
Accepted
time: 547ms
memory: 5320kb

input:

1861
5509 29
5515 29
5550 33
5559 33
5578 36
5601 38
5612 40
5676 48
5686 49
5687 50
5689 50
5696 51
5699 52
5709 52
5722 55
5724 55
5745 58
5761 60
5763 60
5791 65
5798 66
5814 69
5819 69
5903 84
5913 86
5916 87
5941 92
5965 97
5974 98
5979 99
5986 100
5995 102
6038 111
6048 113
6050 114
6051 114
6...

output:

1027161

result:

ok found '1027161.0000000', expected '1027161.0000000', error '0.0000000'

Test #9:

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

input:

1835
680 7513
663 7483
654 7468
651 7461
648 7457
643 7448
630 7425
614 7395
602 7373
600 7371
596 7363
577 7328
570 7313
560 7295
544 7262
539 7253
536 7248
517 7208
516 7206
512 7199
510 7195
499 7172
480 7132
468 7108
453 7075
453 7074
438 7039
437 7039
433 7031
415 6988
412 6984
409 6975
408 697...

output:

13822236

result:

ok found '13822236.0000000', expected '13822236.0000000', error '0.0000000'

Test #10:

score: 0
Accepted
time: 537ms
memory: 5384kb

input:

1858
9984 5375
9983 5383
9981 5413
9981 5418
9979 5441
9978 5446
9977 5459
9974 5485
9972 5503
9972 5514
9971 5514
9969 5535
9969 5536
9965 5570
9964 5585
9955 5656
9952 5678
9950 5691
9948 5701
9946 5720
9945 5723
9945 5725
9944 5731
9941 5757
9939 5767
9935 5790
9935 5791
9930 5820
9929 5830
9927 ...

output:

2490324.500000000000909495

result:

ok found '2490324.5000000', expected '2490324.5000000', error '0.0000000'

Test #11:

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

input:

20
2340 769
3619 197
3795 149
5653 45
6914 383
7134 480
8823 1781
8989 1989
9211 2308
9332 2507
9781 3542
9828 3709
9859 3830
9925 4147
9916 5905
772 2336
1565 1370
1853 1118
1864 1109
2045 969

output:

29346414

result:

ok found '29346414.0000000', expected '29346414.0000000', error '0.0000000'

Test #12:

score: 0
Accepted
time: 9ms
memory: 4436kb

input:

216
9573 7015
9508 7159
9409 7352
9380 7407
9371 7424
9321 7511
9294 7558
9275 7590
9270 7598
9180 7739
9112 7841
9075 7894
8977 8027
8913 8109
8797 8250
8780 8269
8704 8355
8640 8425
8612 8454
8596 8470
8594 8473
8560 8507
8479 8589
8431 8634
8372 8689
8340 8718
8105 8916
8034 8971
7977 9015
7840 9...

output:

36377905.14999076871754369

result:

ok found '36377905.1499908', expected '36377905.1499908', error '0.0000000'

Test #13:

score: 0
Accepted
time: 24ms
memory: 4292kb

input:

406
8048 1039
8053 1043
8176 1141
8299 1247
8324 1267
8352 1293
8379 1318
8416 1351
8422 1358
8472 1405
8479 1412
8499 1431
8510 1443
8517 1448
8517 1449
8563 1496
8606 1540
8616 1551
8664 1601
8673 1610
8686 1625
8703 1643
8744 1689
8755 1701
8763 1711
8785 1737
8797 1750
8928 1910
8951 1939
8982 1...

output:

20479513.01212692330227583

result:

ok found '20479513.0121269', expected '20479513.0121269', error '0.0000000'

Test #14:

score: 0
Accepted
time: 50ms
memory: 4456kb

input:

594
4745 8
4753 8
4784 7
4806 6
4836 4
4846 4
4921 3
4986 2
5042 2
5114 4
5120 3
5233 7
5347 14
5350 14
5359 15
5415 19
5427 20
5455 22
5483 25
5493 27
5494 26
5496 27
5515 28
5521 29
5522 29
5587 36
5621 41
5670 47
5674 48
5691 50
5732 56
5802 67
5821 70
5837 73
5843 73
5869 78
5916 87
5953 93
5973...

output:

13084325.89502227387129096

result:

ok found '13084325.8950223', expected '13084325.8950223', error '0.0000000'

Test #15:

score: 0
Accepted
time: 93ms
memory: 4560kb

input:

774
9982 4596
9983 4615
9983 4619
9984 4624
9984 4627
9985 4645
9988 4680
9989 4700
9993 4765
9995 4823
9995 4826
9996 4851
9996 4884
9997 4896
9997 4922
9998 4993
9998 5000
9997 5086
9997 5105
9996 5116
9997 5117
9996 5157
9995 5158
9995 5162
9992 5236
9992 5250
9991 5257
9989 5288
9987 5327
9983 5...

output:

16822524.66874777024713694

result:

ok found '16822524.6687478', expected '16822524.6687478', error '0.0000000'

Test #16:

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

input:

4
0 0
10000 0
10000 10000
0 10000

output:

100000000

result:

ok found '100000000.0000000', expected '100000000.0000000', error '0.0000000'

Test #17:

score: 0
Accepted
time: 576ms
memory: 5224kb

input:

1999
10000 206
1 206
10000 207
1 207
10000 208
1 208
10000 209
1 209
10000 210
1 210
10000 211
1 211
10000 212
1 212
10000 213
1 213
10000 214
1 214
10000 215
1 215
10000 216
1 216
10000 217
1 217
10000 218
1 218
10000 219
1 219
10000 220
1 220
10000 221
1 221
10000 222
1 222
10000 223
1 223
10000 2...

output:

5000.5

result:

ok found '5000.5000000', expected '5000.5000000', error '0.0000000'

Test #18:

score: 0
Accepted
time: 529ms
memory: 5272kb

input:

1999
2558 4070
7558 9067
2555 4075
7555 9072
2552 4080
7552 9077
2549 4085
7549 9082
2546 4090
7546 9087
2543 4095
7543 9092
2540 4100
7540 9097
2537 4105
7537 9102
2534 4110
7534 9107
2531 4115
7531 9112
2528 4120
7528 9117
2525 4125
7525 9122
2522 4130
7522 9127
2519 4135
7519 9132
2516 4140
7516 ...

output:

20015.52754407051270391094

result:

ok found '20015.5275441', expected '20015.5275441', error '0.0000000'

Test #19:

score: 0
Accepted
time: 559ms
memory: 5296kb

input:

1999
8044 3034
8041 3044
8038 3043
8035 3053
8032 3052
8029 3062
8026 3061
8023 3071
8020 3070
8017 3080
8014 3079
8011 3089
8008 3088
8005 3098
8002 3097
7999 3107
7996 3106
7993 3116
7990 3115
7987 3125
7984 3124
7981 3134
7978 3133
7975 3143
7972 3142
7969 3152
7966 3151
7963 3161
7960 3160
7957 ...

output:

12416.62234580384227911054

result:

ok found '12416.6223458', expected '12416.6223458', error '0.0000000'

Test #20:

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

input:

3
1664 1839
5145 767
5644 8714

output:

14099217.5

result:

ok found '14099217.5000000', expected '14099217.5000000', error '0.0000000'

Test #21:

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

input:

4
5094 2585
5154 4865
5972 9655
5003 6086

output:

388962.3316993955450016074

result:

ok found '388962.3316994', expected '388962.3316994', error '0.0000000'

Test #22:

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

input:

5
3839 2462
6450 9731
917 6915
2220 5164
1430 1649

output:

15630841.30631380591876223

result:

ok found '15630841.3063138', expected '15630841.3063138', error '0.0000000'

Test #23:

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

input:

6
4474 1457
4905 3089
7554 5776
6426 6077
4616 4542
3028 1491

output:

3517836.371496748948175082

result:

ok found '3517836.3714967', expected '3517836.3714967', error '0.0000000'

Test #24:

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

input:

7
5319 5082
5280 6009
5900 8273
4111 5641
2346 6076
4674 4589
5948 4865

output:

920101.5692595524506032234

result:

ok found '920101.5692596', expected '920101.5692596', error '0.0000000'

Test #25:

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

input:

8
4096 3756
5382 4371
7186 1749
9632 4602
9758 4704
7149 6803
3563 8911
1013 2622

output:

20333963.76538616944890236

result:

ok found '20333963.7653862', expected '20333963.7653862', error '0.0000000'

Test #26:

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

input:

9
7720 2038
8160 2661
6427 4528
7007 5869
7399 6513
2037 4071
995 3028
3176 881
5040 1874

output:

16379711.10531968446957762

result:

ok found '16379711.1053197', expected '16379711.1053197', error '0.0000000'

Test #27:

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

input:

10
5757 1393
8096 4772
7059 5458
6743 5903
2827 8013
2719 6272
4013 5299
4392 5065
1849 2006
4954 4503

output:

6259308.473179912989508011

result:

ok found '6259308.4731799', expected '6259308.4731799', error '0.0000000'

Test #28:

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

input:

11
6380 2640
6053 3857
8539 3296
7275 6299
6595 7559
5977 7236
2481 7189
1352 7020
2354 6448
3042 3511
5262 3499

output:

2610035.089641430374285846

result:

ok found '2610035.0896414', expected '2610035.0896414', error '0.0000000'

Test #29:

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

input:

12
4742 5314
3575 5937
1908 5632
3425 2791
4749 4476
4329 252
7368 4691
8318 6692
8011 7335
5673 5882
4724 6947
3994 8628

output:

474170.1614481994502057205

result:

ok found '474170.1614482', expected '474170.1614482', error '0.0000000'

Test #30:

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

input:

13
5477 9803
2323 7271
2200 6085
3516 5451
4596 5080
458 5740
1946 3432
5670 1483
5233 4897
6551 6066
5538 5823
5338 6304
5707 9308

output:

631741.3170850749911551247

result:

ok found '631741.3170851', expected '631741.3170851', error '0.0000000'

Test #31:

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

input:

14
4512 6057
2092 8704
1615 5835
3126 4434
1535 2397
1893 1846
4686 2290
5217 3920
5402 4267
5492 4465
8382 1789
9291 4246
5608 9153
5332 7607

output:

4505176.498228448686859338

result:

ok found '4505176.4982284', expected '4505176.4982284', error '0.0000000'

Test #32:

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

input:

15
4466 5396
1705 4917
3305 4526
1737 3617
3847 4013
5854 2118
5870 2160
6816 2334
7348 1946
6136 4410
8998 4850
9815 5079
7271 8684
6067 9279
5028 6591

output:

2398614.676149464612535667

result:

ok found '2398614.6761495', expected '2398614.6761495', error '0.0000000'

Test #33:

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

input:

16
2696 3357
3395 2997
3757 2086
4827 84
6762 1878
7658 1889
7639 4233
7259 4355
6253 5691
7394 7382
6070 8938
5062 5341
3877 7728
3529 8177
1772 8147
1581 2562

output:

5453.740360503122246882413

result:

ok found '5453.7403605', expected '5453.7403605', error '0.0000000'

Test #34:

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

input:

17
9639 5654
8700 7119
6752 8284
6658 9048
6061 9043
5240 6097
5166 6416
5085 8596
4880 5732
3324 8722
3573 6800
2159 7089
3636 5438
4221 4774
3430 1818
5118 257
5178 431

output:

8859629.518314389681108878

result:

ok found '8859629.5183144', expected '8859629.5183144', error '0.0000000'

Test #35:

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

input:

18
4684 4937
1396 4109
1880 3238
2541 811
3585 601
4837 4007
4735 1936
6971 2430
5309 4810
9367 4665
5106 5027
8195 6885
6551 9079
5139 7637
4917 6186
4783 7309
2686 8721
1754 7471

output:

125428.7536152322309135343

result:

ok found '125428.7536152', expected '125428.7536152', error '0.0000000'

Test #36:

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

input:

16
5000 4332
4332 5000
5000 5668
5668 5000
5000 1761
1761 5000
5000 8239
8239 5000
8914 5000
5000 8914
1086 5000
5000 1086
8205 5000
5000 8205
1795 5000
5000 1795

output:

6521992.75

result:

ok found '6521992.7500000', expected '6521992.7500000', error '0.0000000'

Test #37:

score: 0
Accepted
time: 601ms
memory: 5280kb

input:

2000
5411 5000
5000 5411
4589 5000
5000 4589
5405 5000
5000 5405
4595 5000
5000 4595
5335 5000
5000 5335
4665 5000
5000 4665
5328 5000
5000 5328
4672 5000
5000 4672
5302 5000
5000 5302
4698 5000
5000 4698
5287 5000
5000 5287
4713 5000
5000 4713
5283 5000
5000 5283
4717 5000
5000 4717
5278 5000
5000 ...

output:

63

result:

ok found '63.0000000', expected '63.0000000', error '0.0000000'

Test #38:

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

input:

17
253 449
231 314
60 302
192 231
115 70
230 139
248 89
269 126
304 104
300 141
376 119
332 169
485 216
356 250
464 395
440 408
299 287

output:

2823.585557503602286644195

result:

ok found '2823.5855575', expected '2823.5855575', error '0.0000000'

Test #39:

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

input:

12
1 0
3 0
3 1
5 1
5 3
4 3
4 5
2 5
2 4
0 4
0 2
1 2

output:

1

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #40:

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

input:

32
65 44
446 37
456 81
115 82
70 424
417 449
442 152
160 116
117 376
381 399
396 194
208 161
170 333
344 343
364 231
265 216
258 266
321 275
316 293
223 285
237 191
386 217
361 366
153 342
190 141
419 175
401 426
95 395
149 95
471 132
450 474
33 441

output:

15933.32601130444419901266

result:

ok found '15933.3260113', expected '15933.3260113', error '0.0000000'

Test #41:

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

input:

12
31 458
32 409
82 416
87 196
25 186
36 141
158 144
172 196
125 201
119 421
179 425
176 471

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #42:

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

input:

43
428 479
366 477
287 466
197 439
157 409
124 364
90 305
60 217
52 147
60 80
98 47
164 30
228 22
324 20
362 27
425 44
457 65
469 89
472 126
457 155
436 172
412 171
393 152
388 120
382 82
351 67
283 66
247 68
208 75
174 85
150 108
134 147
138 195
158 264
184 319
229 371
275 404
326 421
386 423
440 4...

output:

9574.730709476954945813532

result:

ok found '9574.7307095', expected '9574.7307095', error '0.0000000'

Test #43:

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

input:

29
132 465
107 334
123 242
114 128
124 50
165 40
177 88
194 170
186 208
190 273
197 332
189 371
189 412
226 425
285 410
286 364
278 312
241 295
215 294
204 283
200 261
208 238
250 234
319 258
332 301
341 381
317 431
220 471
162 472

output:

16853.80365581528372231901

result:

ok found '16853.8036558', expected '16853.8036558', error '0.0000000'

Test #44:

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

input:

16
204 449
280 336
224 287
210 357
92 346
103 129
248 124
238 239
301 314
352 248
276 176
354 85
492 273
453 324
379 269
227 464

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #45:

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

input:

76
148 257
231 232
302 197
344 133
331 91
268 61
175 59
126 95
136 139
166 161
240 159
267 126
238 102
197 114
190 133
166 121
170 100
197 86
243 86
281 110
287 143
259 175
179 191
130 162
97 105
113 66
158 36
229 29
348 33
411 75
422 141
394 197
302 260
187 282
98 316
83 387
111 454
232 463
329 460...

output:

11552.25437455904561545594

result:

ok found '11552.2543746', expected '11552.2543746', error '0.0000000'

Test #46:

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

input:

43
369 304
284 263
213 241
151 202
116 156
125 110
161 72
219 61
331 55
393 82
419 139
412 174
383 194
320 201
249 183
241 145
276 131
292 151
319 163
368 145
361 116
301 98
238 98
159 117
178 185
241 218
325 234
432 273
451 334
395 400
275 424
166 418
101 372
89 312
140 275
193 281
206 312
183 316
...

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #47:

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

input:

14
0 0
10 0
20 10
20 0
30 0
30 50
20 50
20 40
0 50
0 40
20 30
0 30
0 20
20 20

output:

225

result:

ok found '225.0000000', expected '225.0000000', error '0.0000000'

Test #48:

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

input:

14
80 20
100 20
100 30
80 30
100 40
100 50
80 40
80 50
70 50
70 0
80 0
80 10
90 0
100 0

output:

250

result:

ok found '250.0000000', expected '250.0000000', error '0.0000000'

Test #49:

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

input:

6
0 10
10 10
10 0
30 10
20 10
20 20

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #50:

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

input:

6
0 0
1731 1971
6924 0
6924 7884
3462 3942
0 7884

output:

0

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #51:

score: -100
Wrong Answer
time: 617ms
memory: 5676kb

input:

1997
3908 7186
4995 5010
3369 8248
3742 7495
3196 8560
2914 9075
3115 8666
3503 7878
3121 8572
4518 5914
3643 7523
4364 6181
4836 5304
2850 8959
3474 7801
2825 8973
4059 6705
3798 7143
2927 8667
4887 5194
3881 6907
3365 7776
3907 6854
4938 5105
3879 6898
4032 6630
3235 7915
4167 6367
3342 7681
3651 ...

output:

2.983912054332904517650604e-05

result:

wrong answer 1st numbers differ - expected: '0.0000302', found: '0.0000298', error = '0.0000004'