QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#462198 | #784. 旋转卡壳 | lmeowdn | 10 | 1ms | 4088kb | C++14 | 2.4kb | 2024-07-03 15:31:13 | 2024-07-03 15:31:13 |
Judging History
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]);
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;
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
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: 0
Accepted
time: 0ms
memory: 3888kb
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: 0
Accepted
time: 1ms
memory: 3940kb
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: 0
Accepted
time: 0ms
memory: 4088kb
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: 0
Accepted
time: 1ms
memory: 3836kb
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: 0
Accepted
time: 0ms
memory: 3936kb
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: 0
Accepted
time: 0ms
memory: 3888kb
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: 0
Accepted
time: 0ms
memory: 4032kb
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: 0
Accepted
time: 0ms
memory: 4088kb
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: 0
Accepted
time: 0ms
memory: 4020kb
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: 0
Accepted
time: 0ms
memory: 3836kb
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: 0
Accepted
time: 1ms
memory: 4020kb
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: 0
Accepted
time: 0ms
memory: 4036kb
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: 0
Accepted
time: 0ms
memory: 3900kb
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: 0
Accepted
time: 1ms
memory: 4088kb
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: 0
Accepted
time: 0ms
memory: 3832kb
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: 0
Accepted
time: 0ms
memory: 3976kb
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: 0
Accepted
time: 0ms
memory: 3916kb
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: 0
Accepted
time: 0ms
memory: 3888kb
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: 0
Accepted
time: 0ms
memory: 4084kb
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%