题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4570
这个题,省选的时候思路一点没错啊!(╯‵□′)╯︵┻━┻
是我考试的时候心太急了,当然草稿纸太小绝对也是原因之一 (逃
就是推一推式子,发现是个凸包+对勾函数
于是搞一搞范围,求一求极值就可以辣!
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 1000000+9; const double INF = 1e100; struct Point{ #define Vector Point int x,y; inline Point() {} inline Point(int _x, int _y):x(_x),y(_y){} inline bool operator < (const Point &B) const{return (x<B.x)||(x==B.x&&y<B.y);} inline Point operator - (const Point &B) {Point C; C.x=x-B.x; C.y=y-B.y; return C;} inline LL operator * (const Point &B) {return (LL)x*B.y - (LL)y*B.x;} }p[N],con[N]; int n,cnt; double vout = INF; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline void ConvexHull(){ con[++cnt] = p[n]; for (int i=n-1;i;i--) { while (cnt > 1 && (con[cnt]-con[cnt-1])*(p[i]-con[cnt-1]) <= 0LL) cnt--; con[++cnt] = p[i]; } while (cnt > 1 && con[cnt].y <= con[cnt-1].y) cnt--; } int main(){ n = read(); for (int i=1;i<=n;i++) p[i].x = read(), p[i].y = read(); sort(p+1,p+1+n); ConvexHull(); double R, L=INF, MN; for (int i=1;i<=cnt;i++) { Vector v = con[i+1] - con[i]; swap(L, R); L = i!=cnt?(double)-v.y / v.x:0; MN = sqrt((double)con[i].y / con[i].x); if (R < MN) vout = min(vout, con[i].x*R + con[i].y/R + con[i].x + con[i].y); else if (L > MN) vout = min(vout, con[i].x*L + con[i].y/L + con[i].x + con[i].y); else vout = min(vout, con[i].x*MN + con[i].y/MN + con[i].x + con[i].y); } printf("%.4lf\n",vout); return 0; }