QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#355324#2295. Dyson Circleckiseki#AC ✓139ms23268kbC++201.9kb2024-03-16 15:59:092024-03-16 15:59:09

Judging History

This is the latest submission verdict.

  • [2024-03-16 15:59:09]
  • Judged
  • Verdict: AC
  • Time: 139ms
  • Memory: 23268kb
  • [2024-03-16 15:59:09]
  • Submitted

answer

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

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
#include <experimental/iterator>
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  cin >> n;
  vector<pair<int, int>> a(n);
  for (auto &[x, y] : a)
    cin >> x >> y;

  int mxx = -1e9, mix = 1e9, mxy = -1e9, miy = 1e9;
  for (auto [x, y] : a) {
    mxx = max(mxx, x);
    mix = min(mix, x);
    mxy = max(mxy, y);
    miy = min(miy, y);
  }

  int ans = (mxx - mix) * 2 + (mxy - miy) * 2 + 8;
  set<int> major, minor;
  for (auto [x, y] : a) {
    major.insert(x + y);
    minor.insert(x - y);
  }

  for (int x = mix - 1; x <= mxx + 1; ++x) {
    const int y = mxy + 1;
    if (minor.find(x - y) != minor.end()) {
      ans -= x - mix;
      break;
    }
  }
  for (int x = mix - 1; x <= mxx + 1; ++x) {
    const int y = miy - 1;
    if (major.find(x + y) != major.end()) {
      ans -= x - mix;
      break;
    }
  }
  for (int x = mxx + 1; x >= mix - 1; --x) {
    const int y = mxy + 1;
    if (major.find(x + y) != major.end()) {
      ans -= mxx - x;
      break;
    }
  }
  for (int x = mxx + 1; x >= mix - 1; --x) {
    const int y = miy - 1;
    if (minor.find(x - y) != minor.end()) {
      ans -= mxx - x;
      break;
    }
  }

  if ((major.size() == 1) ^ (minor.size() == 1)) {
    ans += 1;
  }

  cout << ans << '\n';
  return 0;
}

詳細信息

Test #1:

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

input:

1
-201504 -209794

output:

4

result:

ok single line: '4'

Test #2:

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

input:

2
23 42
24 43

output:

7

result:

ok single line: '7'

Test #3:

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

input:

2
23 42
24 41

output:

7

result:

ok single line: '7'

Test #4:

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

input:

2
-1000000 -1000000
1000000 1000000

output:

4000005

result:

ok single line: '4000005'

Test #5:

score: 0
Accepted
time: 7ms
memory: 3620kb

input:

2
1000000 -1000000
-1000000 1000000

output:

4000005

result:

ok single line: '4000005'

Test #6:

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

input:

2
-1000000 -1000000
1000000 999999

output:

4000004

result:

ok single line: '4000004'

Test #7:

score: 0
Accepted
time: 8ms
memory: 3572kb

input:

2
-1000000 -1000000
999999 1000000

output:

4000004

result:

ok single line: '4000004'

Test #8:

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

input:

2
1000000 -1000000
-1000000 999999

output:

4000004

result:

ok single line: '4000004'

Test #9:

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

input:

2
1000000 -1000000
-999999 1000000

output:

4000004

result:

ok single line: '4000004'

Test #10:

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

input:

2
4711 -1000000
4711 1000000

output:

4000004

result:

ok single line: '4000004'

Test #11:

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

input:

2
1000000 4711
-1000000 4711

output:

4000004

result:

ok single line: '4000004'

Test #12:

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

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: 3860kb

input:

3
66 -48
-97 45
63 -70

output:

349

result:

ok single line: '349'

Test #14:

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

input:

1
-77 10

output:

4

result:

ok single line: '4'

Test #15:

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

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: 3788kb

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: 3568kb

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: 3568kb

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: 3828kb

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: 3632kb

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: 3564kb

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: 3564kb

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: 3632kb

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: 0ms
memory: 3564kb

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: 3628kb

input:

3
-15 -41
96 70
92 66

output:

227

result:

ok single line: '227'

Test #26:

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

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: 3600kb

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: 3636kb

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: 3856kb

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: 3828kb

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: 3864kb

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: 1ms
memory: 3664kb

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: 0ms
memory: 3624kb

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: 3764kb

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: 3732kb

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: 1ms
memory: 3704kb

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: 90ms
memory: 17176kb

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: 2ms
memory: 3932kb

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: 7ms
memory: 5768kb

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: 139ms
memory: 23004kb

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: 138ms
memory: 23268kb

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: 72ms
memory: 14152kb

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: 0ms
memory: 3824kb

input:

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

output:

8000004

result:

ok single line: '8000004'