QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#122924 | #784. 旋转卡壳 | Zimse__# | 0 | 9ms | 35380kb | C++14 | 2.8kb | 2023-07-11 14:57:45 | 2023-07-11 14:57:47 |
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-05-30 09:00:15]
- hack成功,自动添加数据
- (/hack/642)
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-07-11 14:57:45]
- 提交
answer
// Author:Zimse Data:2023-06-
#include <bits/stdc++.h>
#define pc putchar
#define pb push_back
#define inv fpow
// #define int long long
namespace OI{const int INF=1.001e9,Mod=998244353;int read(){int x=0
,y=1;char c=getchar();while(c<48||57<c){if(c==45)y=-1;c=getchar();}
while(47<c&&c<58)x=x*10+c-48,c=getchar();return x*y;}void wr(int x)
{if(x<0)pc(45),x=-x;if(x>=10)wr(x/10);pc(48+x%10);}void wri(int x){
wr(x),pc(32);}void _wri(int x){wr(x),pc(10);}void iF(const char*x){
freopen(x,"r",stdin);}void oF(const char*x){freopen(x,"w",stdout);}
inline int fpow(long long x,int y=Mod-2){int z=1;while(y){if(y&1)z=
x*z%Mod;x=x*x%Mod,y/=2;}return z;}inline void _max(int&x,int y){if(
x<y)x=y;}inline void _min(int&x,int y){if(y<x)x=y;}inline void _mod
(int&x,int y){(x+=y)%=Mod;}}using namespace OI;using namespace std;
const int N=1.01e6;
const double eps=1e-7;
const double Pi=3.141592653589793;
const double dx[4]={1,1,-1,-1},dy[4]={1,-1,-1,1};
struct point{
double x,y;
point(double x=0,double y=0):x(x),y(y){}
inline point operator + (const point &_)const{return point(x+_.x,y+_.y);}
inline point operator - (const point &_)const{return point(x-_.x,y-_.y);}
inline double operator * (const point &_)const{return x*_.y-y*_.x;}
}p[N],O,stk[N];
int top;
inline double sqdis(point A,point B){
return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}
inline bool cmp_PolarAngle(point A,point B){
double c=(A-O)*(B-O);
if(c>eps)return true;
if(c>-eps)return sqdis(O,A)>sqdis(O,B);
return false;
}
inline bool cmp_X(point A,point B){
return A.x<B.x;
}
signed main(){
int n=read();
double ans=0,mn=1e18;
for(int i=1,x,y;i<=n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
}
O=p[1];
for(int i=1;i<=n;i++)if(p[i].y<O.y||(p[i].y-eps<=O.y&&p[i].x<O.x))O=p[i];
sort(p+1,p+n+1,cmp_PolarAngle);
p[0]=p[n+1]=stk[0]=O;
for(int i=1;i<=n+1;i++){
if(i<=n&&abs((p[i]-O)*(p[i-1]-O))<eps&&sqdis(O,p[i])<sqdis(O,p[i-1]))continue;
while(top>0&&(stk[top]-stk[top-1])*(p[i]-stk[top])<eps){
if(i>n&&top==1)break;
--top;
}
stk[++top]=p[i];
}
for(int i=top;i<top*3;i++)stk[i]=stk[i-top];
int u=0,v=1;
while(u<top){
ans=max(ans,sqdis(stk[u],stk[v]));
ans=max(ans,sqdis(stk[u],stk[v-1]));
ans=max(ans,sqdis(stk[u+1],stk[v]));
ans=max(ans,sqdis(stk[u+1],stk[v-1]));
if(v+1<top*3&&(stk[u+1]-stk[u])*(stk[v+1]-stk[v])>0)++v;
else ++u;
}
if(top==2)ans=sqdis(stk[0],stk[1]);
sort(p+1,p+n+1,cmp_X);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=min(n,i+100);j++)mn=min(mn,sqrt(sqdis(p[i],p[j])));
}
printf("%.7lf %.7lf\n",mn,sqrt(ans));
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 9ms
memory: 35380kb
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:
32759.4349463 274339223.1895614
result:
wrong answer 1st numbers differ - expected: '274339223.1895614', found: '32759.4349463', error = '0.9998806'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%