QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#407158 | #2295. Dyson Circle | thesupermarketisgoingtome# | AC ✓ | 528ms | 99008kb | C++17 | 3.2kb | 2024-05-08 08:37:09 | 2024-05-08 08:37:09 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'