1 条题解
-
1
#include<algorithm> #include<cstring> #include<cstdio> #include<cmath> #define LD double #define LL long long #define Vector Point #define Re register int using namespace std; const int N=1e6+3; const LD eps=1e-8; inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);} int n,t;LD ans=1e18; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } struct Point{int x,y;Point(Re X=0,Re Y=0){x=X,y=Y;}}P[N],cp[N]; inline LL Cro(Vector a,Vector b){return (LL)a.x*b.y-(LL)a.y*b.x;} inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);} inline bool cmp(const Point &A,const Point &B){return A.x!=B.x?A.x<B.x:A.y>B.y;} inline LD getk(Point a,Point b){return (LD)(a.y-b.y)/(a.x-b.x);} inline LD calc(Point a,LD k){return dcmp(k)?a.x+a.y-a.x*k-a.y/k:1e18;} int main(){ // freopen("123.txt","r",stdin); in(n); for(Re i=1;i<=n;++i)in(P[i].x),in(P[i].y); sort(P+1,P+n+1,cmp); for(Re i=1;i<=n;++i){ while(t>1&&Cro(cp[t]-cp[t-1],P[i]-cp[t-1])>=0)--t; cp[++t]=P[i]; } for(Re i=1;i<=t;++i){ LD k=-sqrt((LD)cp[i].y/cp[i].x); if((i==1||dcmp(k-getk(cp[i],cp[i-1]))<=0)&&(i==t||dcmp(k-getk(cp[i],cp[i+1])>=0)))ans=min(ans,calc(cp[i],k)); if(i>1)ans=min(ans,calc(cp[i],getk(cp[i],cp[i-1]))); if(i<t)ans=min(ans,calc(cp[i],getk(cp[i],cp[i+1]))); } printf("%.4lf\n",ans); }
- 1
信息
- ID
- 2227
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 6
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者