QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#373123#3316. Fair Chocolate-CuttingmshcherbaWA 55ms4032kbC++203.7kb2024-04-01 03:03:272024-04-01 03:03:28

Judging History

This is the latest submission verdict.

  • [2024-04-01 03:03:28]
  • Judged
  • Verdict: WA
  • Time: 55ms
  • Memory: 4032kb
  • [2024-04-01 03:03:27]
  • Submitted

answer

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

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const db EPS = 1e-9;
const db INF = 1e9;

template<typename T>
void updMin(T& a, T b)
{
    a = min(a, b);
}

template<typename T>
void updMax(T& a, T b)
{
    a = max(a, b);
}

struct Pt
{
	db x, y;
	Pt operator+(const Pt& p) const
	{
		return {x + p.x, y + p.y};
	}
	Pt operator-(const Pt& p) const
	{
		return {x - p.x, y - p.y};
	}
    Pt operator*(db d) const
	{
		return {x * d, y * d};
	}
    Pt operator/(db d) const
	{
		return {x / d, y / d};
	}
};
db sq(const Pt& p)
{
	return p.x * p.x + p.y * p.y;
}
db abs(const Pt& p)
{
	return sqrt(sq(p));
}
int sgn(db x)
{
	return (EPS < x) - (x < -EPS);
}
Pt perp(const Pt& p)
{
	return {-p.y, p.x};
}
db dot(const Pt& p, const Pt& q)
{
	return p.x * q.x + p.y * q.y;
}
db cross(const Pt& p, const Pt& q)
{
	return p.x * q.y - p.y * q.x;
}
struct Line
{
	Pt n;
	db c;
	Line(const Pt& p, const Pt& q):
		n(perp(q - p)), c(-dot(n, p)) {}
};
bool parallel(const Line& l1, const Line& l2)
{
	return sgn(cross(l1.n, l2.n)) == 0;
}
Pt inter(const Line& l1, const Line& l2)
{
	db d = cross(l1.n, l2.n);
	assert(sgn(d) != 0);
	return perp(l2.n * l1.c - l1.n * l2.c) / d;
}
db areaTriangle(const Pt& a, const Pt& b, const Pt& c)
{
	return abs(cross(b - a, c - a)) / 2.0;
}
db areaPolygon(const vector<Pt>& v)
{
	db area = 0.0;
	int n = SZ(v);
	FOR(i, 0, n)
		area += cross(v[i], v[(i + 1) % n]);
	return abs(area) / 2.0;
}

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
    cout << fixed << setprecision(10);
	int n;
    cin >> n;
    vector<Pt> v(n);
    for (Pt& p : v)
        cin >> p.x >> p.y;
    db totArea = areaPolygon(v);
    db ansMin = INF, ansMax = 0;
    FOR(i, 0, n)
    {
        db s = 0;
        FOR(j, i + 1, i + n)
        {
            s += areaTriangle(v[i], v[(j - 1) % n], v[j % n]);
            db tr1 = areaTriangle(v[i], v[(i + 1) % n], v[j % n]);
            db tr2 = areaTriangle(v[i], v[j % n], v[(j + 1) % n]);
            if (sgn(s - tr1 - totArea / 2) <= 0 && sgn(totArea / 2 - s - tr2) <= 0)
            {
                function<pair<db, db>(db)> f = [&](db alpha) -> pair<db, db>
                {
                    Pt p = v[i] + (v[(i + 1) % n] - v[i]) * alpha;
                    db tr = areaTriangle(p, v[j % n], v[(j + 1) % n]);
                    db beta = (totArea / 2 - s + alpha * tr1) / tr;
                    Pt q = v[j % n] + (v[(j + 1) % n] - v[j % n]) * beta;
                    return {sq(q - p), beta};
                };
                db l = 0, r = 1;
                FOR(it, 0, 74)
                {
                    db m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
                    if (f(m1) < f(m2))
                        r = m2;
                    else
                        l = m1;
                }
                auto [sqd, beta] = f((l + r) / 2);
                if (sgn(beta) >= 0 && sgn(beta - 1) <= 0)
                {
                    updMin(ansMin, sqrt(sqd));
                }
            }
            if (sgn(s - totArea / 2) <= 0 && sgn(totArea / 2 - s - tr2) <= 0)
            {
                Pt p = v[j % n] + (v[(j + 1) % n] - v[j % n]) * ((totArea / 2 - s) / tr2);
                updMax(ansMax, abs(p - v[i]));
            }
        }
    }
    cout << ansMin << "\n" << ansMax << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
0 0
10000 0
10000 10000
0 10000

output:

10000.0000000000
14142.1356237310

result:

ok 2 numbers

Test #2:

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

input:

3
0 0
10000 0
7000 1000

output:

843.0172706741
8514.6931829632

result:

ok 2 numbers

Test #3:

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

input:

6
0 40
100 20
250 40
250 70
100 90
0 70

output:

65.0640709865
251.7935662403

result:

ok 2 numbers

Test #4:

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

input:

3
0 0
10000 10000
5000 5001

output:

0.7070714276
10606.9552770812

result:

ok 2 numbers

Test #5:

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

input:

5
0 0
1000 0
1000 100
500 150
0 100

output:

149.8133155110
1002.8085560066

result:

ok 2 numbers

Test #6:

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

input:

4
0 0
100 0
120 50
20 50

output:

50.0000000000
130.0000000000

result:

ok 2 numbers

Test #7:

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

input:

4
0 0
100 0
110 50
30 50

output:

50.0000000000
117.9237041481

result:

ok 2 numbers

Test #8:

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

input:

4
0 0
100 0
200 1000
150 1000

output:

78.4468251772
1015.1970252123

result:

ok 2 numbers

Test #9:

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

input:

100
5000 0
5300 10
5590 30
5870 60
6140 100
6400 150
6650 210
6890 280
7120 360
7340 450
7550 550
7750 660
7940 780
9220 2060
9340 2250
9450 2450
9550 2660
9640 2880
9720 3110
9790 3350
9850 3600
9900 3860
9940 4130
9970 4410
9990 4700
10000 5000
9990 5300
9970 5590
9940 5870
9900 6140
9850 6400
979...

output:

9994.4490697915
10286.3015705354

result:

ok 2 numbers

Test #10:

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

input:

3
0 0
10000 0
10000 1

output:

0.7071067803
10000.0000125000

result:

ok 2 numbers

Test #11:

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

input:

4
0 0
10 0
10 10
0 10

output:

10.0000000000
14.1421356237

result:

ok 2 numbers

Test #12:

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

input:

4
0 0
10000 0
10000 1
0 1

output:

1.0000000000
10000.0000500000

result:

ok 2 numbers

Test #13:

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

input:

3
0 0
10000 1
9999 1

output:

0.0000707142
9999.5000500025

result:

ok 2 numbers

Test #14:

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

input:

4
0 0
1 0
10000 1
9998 1

output:

0.0001581376
9999.5000500025

result:

ok 2 numbers

Test #15:

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

input:

5
0 0
9999 2000
10000 7000
3334 6334
1 5000

output:

5447.1672968568
12018.2564219652

result:

ok 2 numbers

Test #16:

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

input:

3
0 0
1 0
0 1

output:

0.6435942529
1.1180339887

result:

ok 2 numbers

Test #17:

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

input:

3
9999 0
10000 0
10000 1

output:

0.6435942529
1.1180339887

result:

ok 2 numbers

Test #18:

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

input:

3
0 9999
1 10000
0 10000

output:

0.6435942529
1.1180339887

result:

ok 2 numbers

Test #19:

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

input:

3
10000 9999
10000 10000
9999 10000

output:

0.6435942529
1.1180339887

result:

ok 2 numbers

Test #20:

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

input:

6
1000 5500
2500 1000
6000 1500
8000 4000
6500 8500
3000 8000

output:

6166.4414373283
8500.0000000000

result:

ok 2 numbers

Test #21:

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

input:

6
100 350
101 349
6400 3440
6400 3441
1200 7250
1199 7249

output:

4559.2050019028
6216.7174287969

result:

ok 2 numbers

Test #22:

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

input:

3
0 0
5 0
0 10

output:

3.4356074972
10.3077640640

result:

ok 2 numbers

Test #23:

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

input:

12
1000 4700
2000 4000
3000 3800
4000 3900
5000 4100
6000 4500
6000 5501
5000 5899
4000 6101
3000 6199
2000 6001
1000 5299

output:

2306.4248810736
5035.8713248057

result:

ok 2 numbers

Test #24:

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

input:

100
9999 0
9995 158
9987 316
9976 475
9957 632
9936 789
9907 945
9874 1100
9837 1255
9794 1407
9747 1559
9697 1709
9639 1857
9578 2003
9513 2148
9443 2290
9366 2429
9289 2567
9205 2702
9116 2834
9023 2962
8927 3088
8829 3213
8724 3332
8617 3449
8506 3562
8391 3671
8273 3777
8150 3878
8026 3976
7898 ...

output:

4996.9029661391
9145.2300180026

result:

ok 2 numbers

Test #25:

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

input:

12
8118 5000
7687 6551
6534 7657
5000 8187
3399 7773
2233 6597
1849 5000
2310 3447
3431 2283
4999 1854
6533 2344
7691 3445

output:

5994.1054480952
6312.6615397698

result:

ok 2 numbers

Test #26:

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

input:

12
5000 0
6152 665
6680 1580
6680 2780
5956 4034
5158 4494
3838 4494
2959 3987
2441 3089
2441 1604
2825 939
4451 0

output:

4239.0000000000
4601.5733235638

result:

ok 2 numbers

Test #27:

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

input:

6
9493 6827
4123 8291
2764 8126
233 3849
4751 89
9261 3165

output:

7210.1557805940
9260.5268136401

result:

ok 2 numbers

Test #28:

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

input:

10
9950 7585
9384 8907
6918 9826
749 9053
64 8730
590 4225
1153 2481
1441 2127
3850 289
9659 814

output:

9150.8954945995
11940.5680944398

result:

ok 2 numbers

Test #29:

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

input:

11
9845 5904
6473 9556
5150 9835
4005 9959
2361 9496
225 5244
187 3223
1837 777
4075 322
7218 183
9375 581

output:

9218.6102607152
10782.0340337063

result:

ok 2 numbers

Test #30:

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

input:

10
9995 909
9990 4084
8777 9930
2993 9997
2051 9909
36 9601
543 2264
636 2005
1408 29
8413 439

output:

9349.9772143344
13086.2741614812

result:

ok 2 numbers

Test #31:

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

input:

100
0 102
1 89
2 77
3 66
4 56
5 47
6 39
7 32
8 26
9 21
10 17
11 14
12 12
14 11
17 10
21 9
26 8
32 7
39 6
47 5
56 4
66 3
77 2
89 1
102 0
9898 0
9911 1
9923 2
9934 3
9944 4
9953 5
9961 6
9968 7
9974 8
9979 9
9983 10
9986 11
9988 12
9989 14
9990 17
9991 21
9992 26
9993 32
9994 39
9995 47
9996 56
9997 6...

output:

10000.0000000000
14108.1944982340

result:

ok 2 numbers

Test #32:

score: 0
Accepted
time: 54ms
memory: 3948kb

input:

2171
17751 3646
17807 3669
17824 3676
17870 3695
17899 3707
17940 3724
17993 3746
18005 3751
18060 3774
18103 3792
18134 3805
18184 3826
18203 3834
18248 3853
18274 3864
18333 3889
18366 3903
18406 3920
18453 3940
18507 3963
18514 3966
18572 3991
18623 4013
18667 4032
18704 4048
18734 4061
18787 408...

output:

15277.3418272908
76840.9555330688

result:

ok 2 numbers

Test #33:

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

input:

2174
15738 2229
15784 2242
15837 2257
15897 2274
15964 2293
16030 2312
16089 2329
16141 2344
16186 2357
16255 2377
16310 2393
16375 2412
16416 2424
16474 2441
16535 2459
16579 2472
16643 2491
16690 2505
16747 2522
16814 2542
16877 2561
16930 2577
16973 2590
17029 2607
17088 2625
17137 2640
17199 265...

output:

20273.7481128747
106078.5795898843

result:

ok 2 numbers

Test #34:

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

input:

27
24 62
18 60
13 57
7 51
4 46
2 40
1 33
3 23
5 17
8 12
13 7
18 4
21 3
32 2
43 3
46 4
51 7
56 12
59 17
61 23
63 33
62 40
60 46
57 51
51 57
46 60
40 62

output:

59.9382395573
62.7874046396

result:

ok 2 numbers

Test #35:

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

input:

41
33 82
29 81
26 80
20 77
17 75
9 67
7 64
4 58
3 55
2 51
1 43
3 32
4 28
5 25
8 19
10 16
17 9
20 7
26 4
29 3
42 2
55 3
58 4
64 7
67 9
74 16
76 19
79 25
80 28
81 32
83 43
82 51
81 55
80 58
77 64
75 67
67 75
64 77
58 80
55 81
51 82

output:

79.9409810513
82.7944720936

result:

ok 2 numbers

Test #36:

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

input:

41
42 102
37 101
34 100
24 95
21 93
11 83
9 80
4 70
3 67
2 62
1 53
3 41
4 36
5 33
10 23
12 20
21 11
24 9
34 4
37 3
52 2
67 3
70 4
80 9
83 11
92 20
94 23
99 33
100 36
101 41
103 53
102 62
101 67
100 70
95 80
93 83
83 93
80 95
70 100
67 101
62 102

output:

99.9445521871
102.7950402830

result:

ok 2 numbers

Test #37:

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

input:

57
51 122
46 121
40 119
35 117
33 116
28 113
25 111
13 99
11 96
8 91
7 89
5 84
3 78
2 73
1 63
3 50
4 45
6 39
8 34
9 32
12 27
14 24
25 13
28 11
33 8
35 7
40 5
46 3
62 2
78 3
84 5
89 7
91 8
96 11
99 13
110 24
112 27
115 32
116 34
118 39
120 45
121 50
123 63
122 73
121 78
119 84
117 89
116 91
113 96
11...

output:

119.9415061559
122.7954149551

result:

ok 2 numbers

Test #38:

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

input:

57
60 142
55 141
51 140
48 139
43 137
35 133
29 129
15 115
11 109
7 101
5 96
4 93
3 89
2 84
1 73
3 59
4 54
5 50
6 47
8 42
12 34
16 28
29 15
35 11
43 7
48 5
51 4
55 3
72 2
89 3
93 4
96 5
101 7
109 11
115 15
128 28
132 34
136 42
138 47
139 50
140 54
141 59
143 73
142 84
141 89
140 93
139 96
137 101
13...

output:

139.9395378489
142.7956802828

result:

ok 2 numbers

Test #39:

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

input:

14
32 2
43 3
46 4
51 7
56 12
59 17
61 23
63 33
62 40
60 46
57 51
51 57
46 60
40 62

output:

26.3063589828
55.0999768510

result:

ok 2 numbers

Test #40:

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

input:

21
33 82
29 81
26 80
20 77
17 75
9 67
76 19
79 25
80 28
81 32
83 43
82 51
81 55
80 58
77 64
75 67
67 75
64 77
58 80
55 81
51 82

output:

40.2372491083
74.7993846191

result:

ok 2 numbers

Test #41:

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

input:

21
42 102
37 101
34 100
24 95
21 93
11 83
9 80
4 70
3 67
2 62
1 53
3 41
4 36
5 33
10 23
12 20
83 93
80 95
70 100
67 101
62 102

output:

44.5511735475
90.1661003903

result:

ok 2 numbers

Test #42:

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

input:

29
51 122
46 121
40 119
35 117
33 116
28 113
25 111
13 99
11 96
8 91
7 89
5 84
3 78
2 73
1 63
3 50
4 45
6 39
8 34
9 32
12 27
14 24
25 13
28 11
33 8
35 7
40 5
46 3
62 2

output:

54.7649022607
109.3355514456

result:

ok 2 numbers

Test #43:

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

input:

30
60 142
55 141
51 140
48 139
43 137
35 133
29 129
15 115
11 109
7 101
136 42
138 47
139 50
140 54
141 59
143 73
142 84
141 89
140 93
139 96
137 101
133 109
129 115
115 129
109 133
101 137
96 139
93 140
89 141
84 142

output:

71.8031431193
130.6312408729

result:

ok 2 numbers

Test #44:

score: -100
Wrong Answer
time: 0ms
memory: 3884kb

input:

4
100000 100000
50000 99950
1 99900
50001 99950

output:

0.0010110258
99999.0500004875

result:

wrong answer 1st numbers differ - expected: '0.0010000', found: '0.0010110', error = '0.0000110'