QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#663451#2295. Dyson CircleQFshengxiuAC ✓159ms36944kbC++233.6kb2024-10-21 15:40:412024-10-21 15:40:42

Judging History

This is the latest submission verdict.

  • [2024-10-21 15:40:42]
  • Judged
  • Verdict: AC
  • Time: 159ms
  • Memory: 36944kb
  • [2024-10-21 15:40:41]
  • Submitted

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
const int inf = 1e18;
const double eps = 1e-10;
int n, _, m, k;

class Point
{
public:
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    Point operator+(Point a)
    {
        return Point(a.x + x, a.y + y);
    }
    Point operator-(Point a)
    {
        return Point(x - a.x, y - a.y);
    }
    bool operator<(const Point &a) const
    {
        if (x == a.x)
            return y < a.y;
        return x < a.x;
    }
};

typedef Point Vector;

double cross(Vector a, Vector b)
{
    return a.x * b.y - a.y * b.x;
}

double dot(Vector a, Vector b)
{
    return a.x * b.x + a.y * b.y;
}

bool isclock(Point p0, Point p1, Point p2)
{
    Vector a = p1 - p0;
    Vector b = p2 - p0;
    if (cross(a, b) < -eps)
        return true;
    return false;
}

double getDistance(Point a, Point b)
{
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

typedef vector<Point> Polygon;
Polygon andrewScan(Polygon s)
{
    Polygon u, l;
    if (s.size() < 3)
        return s;
    sort(s.begin(), s.end());
    u.push_back(s[0]);
    u.push_back(s[1]);
    l.push_back(s[s.size() - 1]);
    l.push_back(s[s.size() - 2]);
    // printf("l[n-2]:%.2f %.2f\nl[n-1]:%.2f %.2f\n", l[l.size() - 2].x, l[l.size() - 2].y, l[l.size() - 1].x, l[l.size() - 1].y);
    for (int i = 2; i < s.size(); i++)
    {
        for (int n = u.size(); n >= 2 && isclock(u[n - 2], u[n - 1], s[i]) != true; n--)
        {
            // cout << u[n - 2].x << ' ' << u[n - 2].y << '\n'
            //      << u[n - 1].x << u[n - 1].y << endl;
            u.pop_back();
        }
        u.push_back(s[i]);
    }
    for (int i = s.size() - 3; i >= 0; i--)
    {
        // cout << i << endl;
        for (int n = l.size(); n >= 2 && isclock(l[n - 2], l[n - 1], s[i]) != true; n--)
        {
            // cout << i << endl;
            // printf("del:\nl[n-2]:%.2f %.2f\nl[n-1]:%.2f %.2f\n", l[n - 2].x, l[n - 2].y, l[n - 1].x, l[n - 1].y);

            l.pop_back();
        }

        l.push_back(s[i]);
    }
    // for (auto &p : u)
    //     printf("%.2f %.2f\n", p.x, p.y);
    // printf("yes\n");
    // for (auto &p : l)
    //     printf("%.2f %.2f\n", p.x, p.y);

    for (int i = 1; i < u.size() - 1; i++)
        l.push_back(u[i]);
    return l;
}
Polygon v, v1;
int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        Point a;
        cin >> a.x >> a.y;
        for (int k = 0; k < 4; k++)
            v.emplace_back(a.x + dir[k][0], a.y + dir[k][1]);
        v1.push_back(a);
    }
    if (n == 1)
    {
        cout << 4 << endl;
        return;
    }
    Polygon b = andrewScan(v);

    int ans = 0;
    Polygon c = andrewScan(v1);
    int dx = c[1].x - c[0].x, dy = c[1].y - c[0].y;
    if (abs(dx) == abs(dy))
    {
        bool flag = true;
        for (int i = 2; i < c.size(); i++)
        {
            if (c[i].x - c[i - 1].x == dx && c[i].y - c[i - 1].y == dy)
                continue;
            else
            {
                flag = false;
                break;
            }
        }
        if (flag)
            ans++;
    }
    b.push_back(b.front());
    for (int i = 1; i < b.size(); i++)
    {
        int x = abs(b[i].x - b[i - 1].x);
        int y = abs(b[i].y - b[i - 1].y);
        ans += max(x, y);
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    _ = 1;
    // cin>>_;
    while (_--)
    {
        solve();
    }
}

詳細信息

Test #1:

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

input:

1
-201504 -209794

output:

4

result:

ok single line: '4'

Test #2:

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

input:

2
23 42
24 43

output:

7

result:

ok single line: '7'

Test #3:

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

input:

2
23 42
24 41

output:

7

result:

ok single line: '7'

Test #4:

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

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

input:

2
-1000000 -1000000
1000000 999999

output:

4000004

result:

ok single line: '4000004'

Test #7:

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

input:

2
-1000000 -1000000
999999 1000000

output:

4000004

result:

ok single line: '4000004'

Test #8:

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

input:

2
1000000 -1000000
-1000000 999999

output:

4000004

result:

ok single line: '4000004'

Test #9:

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

input:

2
1000000 -1000000
-999999 1000000

output:

4000004

result:

ok single line: '4000004'

Test #10:

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

input:

2
4711 -1000000
4711 1000000

output:

4000004

result:

ok single line: '4000004'

Test #11:

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

input:

2
1000000 4711
-1000000 4711

output:

4000004

result:

ok single line: '4000004'

Test #12:

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

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

input:

3
66 -48
-97 45
63 -70

output:

349

result:

ok single line: '349'

Test #14:

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

input:

1
-77 10

output:

4

result:

ok single line: '4'

Test #15:

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

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

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

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

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

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

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

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

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

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

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

input:

3
-15 -41
96 70
92 66

output:

227

result:

ok single line: '227'

Test #26:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

input:

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

output:

8000004

result:

ok single line: '8000004'