QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122924#784. 旋转卡壳Zimse__#0 9ms35380kbC++142.8kb2023-07-11 14:57:452023-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:47]
  • 评测
  • 测评结果:0
  • 用时:9ms
  • 内存:35380kb
  • [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%