QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#481509 | #784. 旋转卡壳 | chenyikai# | 0 | 3ms | 11732kb | C++14 | 3.7kb | 2024-07-17 07:55:59 | 2024-07-17 07:55:59 |
Judging History
answer
/*
* Author: $%U%$
* Time: $%Y%$-$%M%$-$%D%$ $%h%$:$%m%$:$%s%$
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(ll i=(a);i<=(b);i++)
#define per(i,a,b) for(ll i=(a);i>=(b);i--)
#define re(i,a,b) for(ll i=(a);i<(b);i++)
#define pe(i,a,b) for(ll i=(a);i>(b);i--)
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline void read(T& r) {
r=0;bool w=0; char ch=getchar();
while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();
while(ch>='0'&&ch<='9') r=r*10+(ch^48), ch=getchar();
r=w?-r:r;
}
template <typename T>
inline void readupp(T& r){
r=0;
char ch=getchar();
while(ch>'Z'||ch<'A')ch=getchar();
r=ch;
}
template <typename T>
inline void readlow(T& r){
r=0;
char ch=getchar();
while(ch>'z'||ch<'a')ch=getchar();
r=ch;
}
template <typename T>
inline void readdig(T& r){
r=0;
char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
r=ch-'0';
}
template <typename T>
inline void readvisi(T& r){
r=0;
char ch=getchar();
while(ch>126||ch<33)ch=getchar();
r=ch;
}
template <typename T>
inline ll readlowstr(T& r){
ll n=0;
char ch=getchar();
while(ch>'z'||ch<'a')ch=getchar();
while(ch<='z'&&ch>='a')r[++n]=ch-'a',ch=getchar();
return n;
}
template <typename T>
inline ll readuppstr(T& r){
ll n=0;
char ch=getchar();
while(ch>'Z'||ch<'A')ch=getchar();
while(ch<='Z'&&ch>='A')r[++n]=ch-'A',ch=getchar();
return n;
}
template <typename T>
inline ll readdigstr(T& r){
ll n=0;
char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch<='9'&&ch>='0')r[++n]=ch-'0',ch=getchar();
return n;
}
template <typename T>
inline ll readvisistr(T& r){
ll n=0;
char ch=getchar();
while(ch>126||ch<33)ch=getchar();
while(ch<=126&&ch>=33)r[++n]=ch,ch=getchar();
return n;
}
const ll MOD=998244353;
ll gcd(ll A,ll B){return B?gcd(B,A%B):A;}
template<typename T>
void chkmax(T&A,T B){if(A<B)A=B;}
template<typename T>
void chkmin(T&A,T B){if(A>B)A=B;}
template<typename T>
T Madd(T A,T B){return A+B>=MOD?A+B-MOD:A+B;}
template<typename T>
T Msub(T A,T B){return A-B<0?A-B+MOD:A-B;}
template<typename T>
void MODed(T &A){A%=MOD;A+=(A<0?MOD:0);}
ll pw(ll A,ll B){
ll res=1;
while(B){
if(B&1)res=res*A%MOD;
A=A*A%MOD;
B>>=1;
}
return res;
}
void _FILE(string s){
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
const ll N=200003,M=3003,INF=2000000000000000007ll;
ll n;
const double eps=1e-9;
struct vect{
double x,y;
vect(){x=0,y=0;}
template<typename TT>
vect(TT a,TT b){x=a,y=b;}
vect operator +(const vect &B){return vect(x+B.x,y+B.y);}
vect operator -(const vect &B){return vect(x-B.x,y-B.y);}
double operator *(const vect&B){return x*B.x+y*B.y;}
double operator ^(const vect&B){return x*B.y-y*B.x;}
double len(){return sqrt(x*x+y*y);}
};
struct line{
vect p,v;
line(){}
line(vect A,vect B){p=A,v=B;}
};
double dist(line A,vect B){
return fabs((B-A.p)^A.v)/A.v.len();
}
vect a[N],b[N];
bool vst[N];
int main(){
read(n);
rep(i,0,n-1)read(a[i].x),read(a[i].y);
rep(i,0,n-1){
if(fabs((a[i]-a[(i+n-1)%n])^(a[(i+1)%n]-a[i]))<eps)vst[i]=1;
}
ll cnt=0;
rep(i,0,n-1)if(!vst[i])b[cnt++]=a[i];
n=cnt;
ll pos1=1,pos2=1;
double ans=0;
rep(i,0,n-1){
line tmp(b[i],b[(i+1)%n]-b[i]);
while(dist(tmp,b[pos1])<dist(tmp,b[(pos1+1)%n])-eps)pos1++;
pos2=pos1;
while(dist(tmp,b[pos2])<dist(tmp,b[(pos2+1)%n])+eps)pos2++;
ans=max(ans,(b[pos1]-b[i]).len());
ans=max(ans,(b[pos1]-b[(i+1)%n]).len());
ans=max(ans,(b[pos2]-b[i]).len());
ans=max(ans,(b[pos2]-b[(i+1)%n]).len());
}
cout<<fixed<<setprecision(9)<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 10
Accepted
time: 3ms
memory: 11732kb
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.189561427
result:
ok found '274339223.1895614', expected '274339223.1895614', error '0.0000000'
Test #2:
score: 0
Accepted
time: 3ms
memory: 11224kb
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.927490622
result:
ok found '262687047.9274906', expected '262687047.9274906', error '0.0000000'
Test #3:
score: -10
Wrong Answer
time: 0ms
memory: 10608kb
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:
257866364.643306613
result:
wrong answer 1st numbers differ - expected: '257868038.6435897', found: '257866364.6433066', error = '0.0000065'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%