QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#481509#784. 旋转卡壳chenyikai#0 3ms11732kbC++143.7kb2024-07-17 07:55:592024-07-17 07:55:59

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-17 07:55:59]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:11732kb
  • [2024-07-17 07:55:59]
  • 提交

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%