QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#407158#2295. Dyson Circlethesupermarketisgoingtome#AC ✓528ms99008kbC++173.2kb2024-05-08 08:37:092024-05-08 08:37:09

Judging History

This is the latest submission verdict.

  • [2024-05-08 08:37:09]
  • Judged
  • Verdict: AC
  • Time: 528ms
  • Memory: 99008kb
  • [2024-05-08 08:37:09]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
    typedef Point P;
    T x, y;
    explicit Point(T x=0, T y=0) : x(x), y(y) {}
    bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
    bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
    P operator+(P p) const { return P(x+p.x, y+p.y); }
    P operator-(P p) const { return P(x-p.x, y-p.y); }
    P operator*(T d) const { return P(x*d, y*d); }
    P operator/(T d) const { return P(x/d, y/d); }
    T dot(P p) const { return x*p.x + y*p.y; }
    T cross(P p) const { return x*p.y - y*p.x; }
    T cross(P a, P b) const { return (a-*this).cross(b-*this); }
    T dist2() const { return x*x + y*y; }
    double dist() const { return sqrt((double)dist2()); }
    // angle to x-axis in interval [-pi, pi]
    double angle() const { return atan2(y, x); }
    P unit() const { return *this/dist(); } // makes dist()=1
    P perp() const { return P(-y, x); } // rotates +90 degrees
    P normal() const { return perp().unit(); }
    // returns point rotated 'a' radians ccw around the origin
    P rotate(double a) const {
        return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
    friend ostream& operator<<(ostream& os, P p) {
        return os << "(" << p.x << "," << p.y << ")"; }
};
typedef Point<ll> P;
vector<P> convexHull(vector<P> pts) {
    if (sz(pts) <= 1) return pts;
    sort(all(pts));
    vector<P> h(sz(pts)+1);
    int s = 0, t = 0;
    for (int it = 2; it--; s = --t, reverse(all(pts)))
        for (P p : pts) {
            while (t >= s + 2 && h[t-2].cross(h[t-1], p) <= 0) t--;
            h[t++] = p;
        }
    return {h.begin(), h.begin() + t - (t == 2 && h[0] == h[1])};
}
int same(vector<P>a){
    sort(a.begin(),a.end());
    set<int>s;
    set<int>t;
    for(auto p: a){
        s.insert(p.x-p.y);
        t.insert(p.x+p.y);
    }
    if(s.size() == 1 || t.size() == 1){
        int v = a.back().x - a[0].x;
        return 2*v+5;
    }
    return 0;
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    vector<P>arr(n);
    for(int i = 0; i<n; i++){
        int x,y;
        cin >> x >> y;
        arr[i] = P{x,y};
    }
    if(n==1){
        cout << "4\n";
        return 0;
    }
    int v = same(arr);
    if(v>0){
        cout << v << '\n';
        return 0;
    }
    set<P>s;
    vector<int>dx = {-1,0,1,0};
    vector<int>dy = {0,1,0,-1};
    for(int i = 0; i<n; i++){
        for(int d = 0; d<4; d++){
            P p = arr[i] + P{dx[d],dy[d]};
            s.insert(p);
        }
    }
    vector<P>vec;
    for(auto nxt: s){
        vec.push_back(nxt);
    }
    vector<P>a = convexHull(vec);
    int ans = a.size();

    a.push_back(a[0]);
    for(int i = 1; i<a.size(); i++){
        int v = max(abs(a[i-1].x-a[i].x),abs(a[i].y-a[i-1].y))-1;
        ans+=v;
    }
    cout << ans << '\n';
    return 0;
}

详细

Test #1:

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

input:

1
-201504 -209794

output:

4

result:

ok single line: '4'

Test #2:

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

input:

2
23 42
24 43

output:

7

result:

ok single line: '7'

Test #3:

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

input:

2
23 42
24 41

output:

7

result:

ok single line: '7'

Test #4:

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

input:

2
-1000000 -1000000
1000000 1000000

output:

4000005

result:

ok single line: '4000005'

Test #5:

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

input:

2
1000000 -1000000
-1000000 1000000

output:

4000005

result:

ok single line: '4000005'

Test #6:

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

input:

2
-1000000 -1000000
1000000 999999

output:

4000004

result:

ok single line: '4000004'

Test #7:

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

input:

2
-1000000 -1000000
999999 1000000

output:

4000004

result:

ok single line: '4000004'

Test #8:

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

input:

2
1000000 -1000000
-1000000 999999

output:

4000004

result:

ok single line: '4000004'

Test #9:

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

input:

2
1000000 -1000000
-999999 1000000

output:

4000004

result:

ok single line: '4000004'

Test #10:

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

input:

2
4711 -1000000
4711 1000000

output:

4000004

result:

ok single line: '4000004'

Test #11:

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

input:

2
1000000 4711
-1000000 4711

output:

4000004

result:

ok single line: '4000004'

Test #12:

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

input:

7
-53 94
-71 20
-93 -75
62 30
-90 36
22 -45
-17 -28

output:

478

result:

ok single line: '478'

Test #13:

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

input:

3
66 -48
-97 45
63 -70

output:

349

result:

ok single line: '349'

Test #14:

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

input:

1
-77 10

output:

4

result:

ok single line: '4'

Test #15:

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

input:

4
60 83
20 -33
-69 51
54 -60

output:

399

result:

ok single line: '399'

Test #16:

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

input:

4
2 70
66 -44
13 -23
-61 -11

output:

326

result:

ok single line: '326'

Test #17:

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

input:

10
-93 -97
-9 95
-35 94
-68 -16
-58 37
19 -99
-29 23
14 -60
-37 -48
-47 -99

output:

527

result:

ok single line: '527'

Test #18:

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

input:

10
18 -100
-24 24
-75 -89
-42 8
-80 62
93 25
-98 -19
-51 72
4 32
25 25

output:

546

result:

ok single line: '546'

Test #19:

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

input:

6
37 12
29 -27
-62 -50
11 -53
44 -15
-77 70

output:

376

result:

ok single line: '376'

Test #20:

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

input:

4
-6 -48
-64 -37
80 -5
3 64

output:

326

result:

ok single line: '326'

Test #21:

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

input:

8
-16 -72
-86 -53
90 -57
-59 28
56 47
91 13
-60 -21
-78 41

output:

513

result:

ok single line: '513'

Test #22:

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

input:

8
76 -67
-88 97
-20 29
-50 59
-39 48
27 -18
34 -25
56 -47

output:

333

result:

ok single line: '333'

Test #23:

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

input:

8
31 74
-53 -10
21 64
30 73
57 100
-52 -9
15 58
50 93

output:

225

result:

ok single line: '225'

Test #24:

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

input:

9
29 -3
96 64
2 -30
49 17
-32 -64
27 -5
55 23
21 -11
-66 -98

output:

329

result:

ok single line: '329'

Test #25:

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

input:

3
-15 -41
96 70
92 66

output:

227

result:

ok single line: '227'

Test #26:

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

input:

9
20 37
31 26
72 -15
-25 82
58 -1
76 -19
22 35
26 31
34 23

output:

207

result:

ok single line: '207'

Test #27:

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

input:

9
-13 -85
-98 0
-96 -2
-12 -86
-82 -16
-80 -18
-6 -92
-70 -28
-93 -5

output:

189

result:

ok single line: '189'

Test #28:

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

input:

8
-99 -79
-34 -14
68 88
-42 -22
-28 -8
6 26
4 24
14 34

output:

339

result:

ok single line: '339'

Test #29:

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

input:

6
-49 -72
-6 -29
61 38
92 69
-33 -56
-3 -26

output:

287

result:

ok single line: '287'

Test #30:

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

input:

8
26 -95
25 -94
-54 -15
-15 -54
22 -91
-39 -30
-50 -19
-25 -44

output:

165

result:

ok single line: '165'

Test #31:

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

input:

9
67 33
74 26
15 85
18 82
37 63
50 50
25 75
65 35
44 56

output:

123

result:

ok single line: '123'

Test #32:

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

input:

928
9500 1342
-7881 -5408
-6068 2272
764 -9877
-5181 -4671
2693 -1209
-3812 740
-7435 -7344
651 -3291
-4600 5063
8754 -328
1773 2138
7600 -74
-1670 -3442
6797 -4644
-2210 1409
7503 -6035
-958 9285
193 -5508
7249 -657
-5131 -8697
5096 -7891
-9423 2007
-3245 -3779
6887 -9459
-9269 647
6908 6326
3645 6...

output:

77873

result:

ok single line: '77873'

Test #33:

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

input:

169
6936 5081
5618 8088
-5765 -9632
5222 -8105
6474 -3280
-2624 9418
-3808 4388
-5907 3256
-2304 -1222
-2858 9116
3688 562
8021 -2717
9742 -2383
-2260 643
-7695 -3694
5694 809
9918 7229
7157 -8613
6628 9313
91 -4074
-5235 -1485
-7080 8703
7513 1894
-9582 -588
-2942 788
3007 -1539
-7216 -3973
3812 -6...

output:

70155

result:

ok single line: '70155'

Test #34:

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

input:

982
1816 -5967
-4260 -1809
-2231 -2712
844 -4972
-9502 -5807
4573 803
-165 -9542
5213 -4586
8204 -9338
-5987 5346
-2776 259
-8713 1220
5567 -9971
-9162 1136
-7821 3489
6955 1572
-3224 3616
-3771 -6699
8798 -5005
-4546 8265
4880 7595
8935 -7607
-7651 3702
-2959 -7771
4835 3799
4721 -5351
-3920 7617
9...

output:

76110

result:

ok single line: '76110'

Test #35:

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

input:

948
7264 8780
-8677 -2160
8517 -1833
1779 -8096
-372 -2433
9531 413
-2236 9743
9776 -2165
-2317 9848
-3255 7550
9080 -1872
1160 8144
360 -8478
8353 -4707
3244 7922
-1059 -2763
1873 -4106
6868 -34
5996 -8327
8969 722
-6024 1189
4137 589
3556 590
-1135 7561
6797 7066
3761 4542
6382 9066
3114 8561
9398...

output:

75323

result:

ok single line: '75323'

Test #36:

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

input:

730
-1743 -5203
-8233 913
-3735 1872
5071 2264
7527 2290
7827 4860
-5248 -9172
2768 7223
-4685 -2793
-1314 -3543
-331 -9886
-8989 4887
7985 8844
5984 -50
-9607 2860
-5311 5312
8426 1651
424 6430
8629 -2438
303 -309
-897 7570
8705 -3474
944 -8738
-6588 -1574
9113 3324
-5477 -5032
7654 -9986
-5007 710...

output:

74922

result:

ok single line: '74922'

Test #37:

score: 0
Accepted
time: 313ms
memory: 72912kb

input:

141317
-274942 -682201
-186052 -834038
-100601 61727
-944698 131823
635222 867300
-239410 817250
374969 -790867
-634764 -180132
170347 -815536
-517742 -6722
233434 -165940
-664181 523395
-705446 -753154
-793193 -360072
273024 -790792
581243 464110
-275845 -813563
725947 -118324
-797098 250331
884513...

output:

7974752

result:

ok single line: '7974752'

Test #38:

score: 0
Accepted
time: 5ms
memory: 4748kb

input:

3219
799461 -763629
-845801 -828705
436218 602504
64013 119629
-145168 23186
336602 -109589
602702 586542
131754 579855
-920365 -764639
179226 954008
-867415 959133
276457 158237
974550 316414
163430 264439
-647957 562192
-544042 -675651
-21138 -853886
-270398 525889
633758 731146
859843 789223
-553...

output:

7897260

result:

ok single line: '7897260'

Test #39:

score: 0
Accepted
time: 29ms
memory: 12944kb

input:

20296
872721 871788
928806 299409
352690 -755652
-332775 70799
-458562 664306
796842 -379164
-370289 557717
-435954 916731
-394675 -15900
417387 -920207
-493742 -157086
873833 -40616
79906 840493
538679 -450830
181308 395172
-880496 536539
-253127 153008
-759596 -968053
-144713 405014
-305183 -13728...

output:

7930553

result:

ok single line: '7930553'

Test #40:

score: 0
Accepted
time: 528ms
memory: 99008kb

input:

200000
-282804 959107
-747453 48772
-484768 -296154
482756 -763650
-435017 693599
-978517 640299
-121371 -683431
-77727 -710560
703571 885689
-335235 847996
-620488 891368
851990 -144059
56422 75285
853527 -382440
-274932 662212
654877 -205493
166985 -663763
-80386 -608151
749100 794472
685651 42769...

output:

7970085

result:

ok single line: '7970085'

Test #41:

score: 0
Accepted
time: 486ms
memory: 98172kb

input:

200000
-1000000 383683
1000000 905265
-474152 -1000000
787627 1000000
-1000000 -820522
-840177 1000000
1000000 -88481
-1000000 -170781
-172081 -1000000
-367521 -1000000
-766211 -1000000
-377722 -1000000
1000000 -58096
-1000000 -11022
-235995 -1000000
-1000000 -924069
396030 1000000
1000000 495411
49...

output:

7999928

result:

ok single line: '7999928'

Test #42:

score: 0
Accepted
time: 71ms
memory: 18800kb

input:

200000
-113124 681399
-646832 147691
105913 900436
-782103 12420
-254677 539846
-75306 719217
32514 827037
71770 866293
-404302 390221
-714475 80048
91667 886190
-728326 66197
-887910 -93387
-440470 354053
-301100 493423
-769098 25425
-803965 -9442
120598 915121
-74363 720160
124557 919080
-124198 6...

output:

2410937

result:

ok single line: '2410937'

Test #43:

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

input:

4
-1000000 -1000000
-1000000 1000000
1000000 -1000000
1000000 1000000

output:

8000004

result:

ok single line: '8000004'