QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#462192#784. 旋转卡壳lmeowdn10 1ms3988kbC++142.3kb2024-07-03 15:29:062024-07-03 15:29:09

Judging History

你现在查看的是最新测评结果

  • [2024-10-16 12:18:36]
  • hack成功,自动添加数据
  • (/hack/1005)
  • [2024-09-24 16:55:39]
  • hack成功,自动添加数据
  • (/hack/888)
  • [2024-07-31 21:52:32]
  • hack成功,自动添加数据
  • (/hack/764)
  • [2024-07-31 21:47:53]
  • hack成功,自动添加数据
  • (/hack/763)
  • [2024-07-03 15:29:09]
  • 评测
  • 测评结果:10
  • 用时:1ms
  • 内存:3988kb
  • [2024-07-03 15:29:06]
  • 提交

answer

//Shirasu Azusa 2024.7
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x)  {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x)  {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x)  {return (x==0?-1:__builtin_ctzll(x));}

#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int Vi=(a);i>=(b);i--)
typedef pair<int,int> pii;  
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();} 
  return x*w;
}

const ld eps=1e-11;
int cmp(ld a,ld b) { //a<b
  if(b-eps<=a&&a<=b+eps) return 0;
  else if(a<b) return 1; else return -1;
}
struct vec{ld x,y;};
ld operator ^ (vec a,vec b) {return a.x*b.y-a.y*b.x;}
vec operator - (vec a,vec b) {return (vec){a.x-b.x,a.y-b.y};}
ld dis(vec a,vec b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
ld area(vec a,vec b,vec c) {
  ld ans=(a-b)^(a-c);
  if(ans<0) ans=-ans; return ans;
}

signed main() {
  int n=read(); vector<vec> p(n);
  rep(i,0,n-1) p[i].x=read(), p[i].y=read(); ld ans=0;
  vector<vec> q; q.reserve(n);
  rep(i,0,n-1) {
    int x=(i+(n-1))%n, y=(i+1)%n;
    if(cmp((p[i]-p[x])^(p[i]-p[y]),0)) q.eb(p[i]);
    else if((p[i].x<p[x].x)==(p[i].x<p[y].x)) q.eb(p[i]);
  } swap(p,q);
  if(p.size()<=2) {
    printf("%.10Lf\n",dis(p[0],p[1]));
    return 0;
  }
  rep(i,0,n-1) {
    int x=(i+(n-1))%n, y=(i+1)%n;
    assert(cmp((p[i]-p[x])^(p[i]-p[y]),0));
  }
  for(int i=0,j=2;i<n;i++) {
    while(area(p[i],p[(i+1)%n],p[j])<=area(p[i],p[(i+1)%n],p[(j+1)%n])) j=(j+1)%n;
    chmax(ans,max(max(dis(p[i],p[j]),dis(p[i],p[(i+1)%n])),dis(p[j],p[(i+1)%n])));
  }
  printf("%.10Lf\n",ans);
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

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

input:

1000
0 0
-997615 -8573
-1988394 -28911
-2726572 -44296
-3491635 -60392
-4419752 -82814
-5298550 -105946
-5723430 -118453
-6608257 -147267
-7034966 -161982
-7563964 -181682
-8507871 -222865
-9499799 -271846
-10090186 -303547
-10400262 -322989
-10614073 -339725
-11081438 -378596
-11791568 -439127
-127...

output:

274339223.1895613901

result:

ok found '274339223.1895614', expected '274339223.1895614', error '0.0000000'

Test #2:

score: 10
Accepted
time: 1ms
memory: 3724kb

input:

1000
0 0
-887614 -1937
-1459359 -3808
-2421409 -24096
-3273181 -48456
-3917594 -76664
-4402753 -100164
-5375022 -150897
-5993935 -192089
-6587159 -238825
-7549680 -333298
-8330993 -416479
-9244392 -515027
-10010900 -598589
-10374584 -640275
-10767641 -686907
-11173081 -741316
-11821952 -833327
-1260...

output:

262687047.9274906333

result:

ok found '262687047.9274906', expected '262687047.9274906', error '0.0000000'

Test #3:

score: 10
Accepted
time: 1ms
memory: 3900kb

input:

1000
0 0
-631055 -2758
-1328409 -7463
-2248672 -20536
-2412978 -23564
-2659543 -28441
-3383179 -43406
-4183375 -64326
-4856658 -88337
-5799682 -134822
-6757348 -189404
-7132846 -212164
-7563226 -242116
-8368716 -300012
-9321463 -381770
-9831821 -432746
-10409503 -491057
-11360852 -607259
-11874199 -...

output:

257868038.6435896887

result:

ok found '257868038.6435897', expected '257868038.6435897', error '0.0000000'

Test #4:

score: 10
Accepted
time: 0ms
memory: 3856kb

input:

1000
0 0
-48652 -588
-951356 -20091
-1517426 -33325
-1965414 -51971
-2466111 -74904
-3046762 -103888
-3555833 -132002
-3976901 -156059
-4972848 -245498
-5921476 -332492
-6353035 -375491
-7327511 -496188
-7939064 -575429
-8842272 -694656
-9246222 -756797
-9771758 -860630
-10633761 -1031205
-10981774 ...

output:

259539672.4804533867

result:

ok found '259539672.4804534', expected '259539672.4804534', error '0.0000000'

Test #5:

score: 10
Accepted
time: 0ms
memory: 3904kb

input:

1000
0 0
-456569 -2668
-1141521 -7887
-1270801 -8967
-1971135 -21206
-2919889 -38188
-3903859 -71231
-4752603 -107450
-5508682 -143873
-6214620 -183392
-6718977 -212193
-7452291 -271600
-8408796 -354998
-9261882 -432674
-9528618 -457608
-10099091 -513153
-10320120 -535958
-11067358 -614356
-12050731...

output:

250217366.4826218512

result:

ok found '250217366.4826218', expected '250217366.4826218', error '0.0000000'

Test #6:

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

input:

1000
0 0
-794019 -17307
-1389128 -41522
-1928884 -68000
-2530256 -103641
-3335109 -158872
-4273633 -225636
-4655012 -253747
-5584931 -329387
-6190262 -382029
-6657521 -422826
-7445510 -497270
-8092482 -562235
-8879759 -646264
-9688106 -745847
-10545954 -857573
-11350736 -962711
-12106702 -1066386
-1...

output:

256130723.0053680089

result:

ok found '256130723.0053680', expected '256130723.0053680', error '0.0000000'

Test #7:

score: 10
Accepted
time: 1ms
memory: 3988kb

input:

1000
0 0
-785524 -1241
-1228373 -2123
-1584480 -5108
-2516949 -19826
-3109735 -51256
-3799285 -95138
-4215892 -125263
-5144743 -202941
-6071171 -287679
-6844072 -376760
-7786583 -487933
-8491316 -575443
-9458832 -700691
-9848966 -756816
-10135682 -798578
-11100151 -940696
-11527785 -1004652
-1221960...

output:

268992022.0570692390

result:

ok found '268992022.0570692', expected '268992022.0570692', error '0.0000000'

Test #8:

score: 10
Accepted
time: 1ms
memory: 3936kb

input:

1000
0 0
-787651 -697
-1319793 -8691
-1545057 -12462
-2239671 -24650
-2487763 -36810
-2983386 -61694
-3408212 -85910
-3650815 -105325
-4268088 -155258
-5088483 -225550
-5720403 -280762
-6036913 -309102
-6663280 -365291
-7656626 -456948
-8462737 -538137
-9318271 -628471
-9704990 -671367
-10363047 -74...

output:

251395356.7229873281

result:

ok found '251395356.7229873', expected '251395356.7229873', error '0.0000000'

Test #9:

score: 10
Accepted
time: 1ms
memory: 3900kb

input:

1000
0 0
-895815 -18037
-1536713 -40507
-2439825 -73040
-2896761 -94230
-3815334 -138606
-4520738 -176711
-4997585 -208924
-5399492 -237632
-5629592 -254751
-6518310 -320902
-7084766 -367663
-7724052 -423029
-8475256 -492590
-9071702 -551527
-9798581 -626155
-10535448 -702512
-11155572 -768931
-1208...

output:

259639018.6166957476

result:

ok found '259639018.6166958', expected '259639018.6166958', error '0.0000000'

Test #10:

score: 10
Accepted
time: 1ms
memory: 3724kb

input:

1000
0 0
-837332 -2192
-1593910 -10845
-2320576 -25425
-3294539 -45660
-4178010 -82673
-4936159 -128518
-5796274 -190640
-6313517 -228540
-7131129 -291797
-7751205 -354513
-8357330 -419926
-9355375 -542247
-9783911 -596434
-10313681 -667126
-10377189 -675659
-10824619 -750345
-11653618 -894218
-1234...

output:

267554454.1762451354

result:

ok found '267554454.1762451', expected '267554454.1762451', error '0.0000000'

Test #11:

score: 10
Accepted
time: 1ms
memory: 3928kb

input:

1000
0 0
-758133 -3909
-1146524 -7212
-1823781 -16200
-2561994 -26923
-3448934 -43815
-4337557 -80953
-4912706 -106752
-5770093 -182352
-6645519 -261073
-7156648 -309532
-7882740 -380211
-8731241 -470527
-9265139 -532092
-10083113 -633235
-10767248 -721935
-11729364 -862416
-12112647 -921658
-128310...

output:

259903024.7335910267

result:

ok found '259903024.7335910', expected '259903024.7335910', error '0.0000000'

Test #12:

score: 10
Accepted
time: 1ms
memory: 3928kb

input:

1000
0 0
-220082 -1509
-1148190 -9207
-2108923 -22196
-2713299 -30623
-3364648 -43866
-3891571 -54675
-4300261 -63335
-4622311 -72814
-5235380 -91992
-5680720 -106355
-6138401 -121807
-7013302 -160828
-7784753 -195568
-8750494 -245022
-9681201 -295430
-10320328 -334255
-11256371 -407963
-12199734 -4...

output:

261658565.5826949610

result:

ok found '261658565.5826949', expected '261658565.5826949', error '0.0000000'

Test #13:

score: 10
Accepted
time: 1ms
memory: 3916kb

input:

1000
0 0
-425515 -4558
-1293469 -14675
-1990220 -30271
-2703160 -49015
-3455818 -76450
-4210140 -107243
-4530367 -120805
-5136478 -158180
-5732363 -196472
-6247394 -230823
-7100635 -290064
-7703961 -335663
-8091361 -368200
-8752153 -427341
-9433796 -491521
-10139006 -563945
-10984402 -653149
-113386...

output:

256353710.9730163317

result:

ok found '256353710.9730163', expected '256353710.9730163', error '0.0000000'

Test #14:

score: 10
Accepted
time: 1ms
memory: 3828kb

input:

1000
0 0
-572806 -2255
-1477072 -15611
-1643871 -18681
-2578790 -51107
-3303402 -86192
-4032032 -123256
-4540711 -150307
-5462171 -206756
-6377222 -264514
-6921545 -316752
-7623842 -390821
-8329739 -466169
-9034451 -568935
-9600887 -653814
-9729771 -674650
-10461476 -795876
-11348904 -952387
-117122...

output:

255498134.5157807233

result:

ok found '255498134.5157807', expected '255498134.5157807', error '0.0000000'

Test #15:

score: 10
Accepted
time: 1ms
memory: 3772kb

input:

1000
0 0
-723350 -3997
-1405147 -10223
-2296494 -21394
-2876280 -32357
-3572827 -51397
-4452032 -87137
-4953249 -111910
-5388609 -141252
-5731586 -165403
-6101332 -197003
-6884756 -282055
-7719066 -372715
-8101214 -415308
-8855617 -516206
-9316024 -579909
-10091662 -705732
-10621099 -799022
-1137369...

output:

258992362.5300114231

result:

ok found '258992362.5300114', expected '258992362.5300114', error '0.0000000'

Test #16:

score: 10
Accepted
time: 1ms
memory: 3940kb

input:

1000
0 0
-638945 -769
-1345094 -2633
-2049372 -9786
-3043001 -20660
-3832821 -40968
-4616354 -61996
-5489016 -89554
-6075577 -112116
-7059918 -153506
-7917375 -193461
-8704241 -235730
-9411173 -289585
-9928254 -332456
-10816688 -407937
-11522358 -469782
-12333778 -541183
-12532282 -560003
-13293480 ...

output:

260884926.0498460651

result:

ok found '260884926.0498461', expected '260884926.0498461', error '0.0000000'

Test #17:

score: 10
Accepted
time: 1ms
memory: 3772kb

input:

1000
0 0
-929784 -9273
-1222089 -14360
-1633168 -22589
-2271669 -42262
-2863939 -61639
-3538074 -85549
-4537727 -127500
-5529674 -172462
-6106076 -217405
-6615381 -262810
-7383575 -342936
-8289266 -445052
-8474592 -467243
-9285779 -564519
-10059545 -662251
-10774681 -753541
-11666601 -869701
-120587...

output:

259788149.3996045251

result:

ok found '259788149.3996045', expected '259788149.3996045', error '0.0000000'

Test #18:

score: 10
Accepted
time: 1ms
memory: 3824kb

input:

1000
0 0
-436597 -2249
-897574 -4839
-1763026 -9858
-2199595 -14239
-2837069 -24431
-3656371 -67025
-4153771 -93216
-5062244 -151716
-5634320 -190859
-6503474 -278174
-7250273 -366225
-7276046 -369834
-7806600 -448708
-8317734 -530915
-8905662 -634997
-9766507 -790590
-9973653 -831916
-10555366 -955...

output:

277834510.7780300392

result:

ok found '277834510.7780300', expected '277834510.7780300', error '0.0000000'

Test #19:

score: 10
Accepted
time: 1ms
memory: 3776kb

input:

1000
0 0
-499456 -5028
-1395210 -19193
-2095999 -36599
-2278240 -43145
-2754419 -63055
-3701264 -104359
-4078225 -133214
-4292562 -151446
-5087031 -220375
-5649235 -277762
-6403916 -358749
-7403700 -470022
-7940233 -537110
-8433330 -607694
-9376563 -746831
-9903004 -831307
-10718505 -965214
-1171369...

output:

261984352.6271107761

result:

ok found '261984352.6271108', expected '261984352.6271108', error '0.0000000'

Test #20:

score: 10
Accepted
time: 1ms
memory: 3916kb

input:

1000
0 0
-347123 -2330
-1296972 -12856
-2114794 -28811
-3005647 -54768
-3802579 -79440
-4777546 -118441
-5386348 -146049
-6230831 -184743
-7083665 -250364
-7963538 -324047
-8621014 -381656
-9065618 -421654
-9883960 -496406
-10349110 -541972
-11146897 -621572
-12108943 -718091
-12921588 -803916
-1348...

output:

265979549.5809911793

result:

ok found '265979549.5809912', expected '265979549.5809912', error '0.0000000'

Subtask #2:

score: 0
Runtime Error

Dependency #1:

100%
Accepted

Test #21:

score: 0
Runtime Error

input:

30000
0 0
-27842 -9
-56782 -24
-64412 -29
-91618 -47
-121087 -68
-152541 -123
-182316 -183
-212916 -274
-234159 -341
-266126 -446
-289328 -523
-317883 -637
-340594 -728
-350940 -781
-374263 -905
-400736 -1046
-427862 -1199
-450458 -1327
-465289 -1413
-485809 -1534
-517032 -1724
-548368 -1921
-576015...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%