题目传送门：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;
}
Hi, Neat post. There’s an issue together with your site in internet explorer, would test this?
IE still is the market chief and a large element of
other folks will omit your magnificent writing due to this problem.
Hello just wanted to give you a brief heads up and let you know a few
of the pictures aren’t loading properly. I’m not sure why
but I think its a linking issue. I’ve tried it in two different web browsers and both show the
same outcome.
My family members always say that I am wasting my time here at net, except I know
I am getting experience all the time by reading thes fastidious articles.
Since the admin of this web site is working,
no question very quickly it will be well-known, due to its quality contents.
Greetings from Carolina! I’m bored to death at work so I decided to
check out your website on my iphone during lunch break.
I love the knowledge you present here and can’t wait to
take a look when I get home. I’m shocked at how fast your blog loaded on my cell phone ..
I’m not even using WIFI, just 3G .. Anyhow,
great site!
Unquestionably believe that which you stated.
Your favorite reason seemed to be on the web the easiest thing to be aware of.
I say to you, I definitely get irked while people think about worries that they plainly don’t know about.
You managed to hit the nail upon the top and defined out the whole
thing without having side-effects , people
can take a signal. Will probably be back to get more.
Thanks
Howdy! This post couldn’t be written any better! Going through this
article reminds me of my previous roommate! He constantly kept
preaching about this. I will forward this post to him. Fairly certain he’ll have a great read.
Thank you for sharing!
Hi there it’s me, I am also visiting this site daily,
this web site is genuinely fastidious and the viewers are actually sharing nice thoughts.
Wow that was strange. I just wrote an incredibly
long comment but after I clicked submit my comment
didn’t appear. Grrrr… well I’m not writing all that over again. Anyways, just wanted to say excellent blog!
Thanks for the auspicious writeup. It actually was a amusement account it.
Look complex to far brought agreeable from you! However, how can we be
in contact?
Hi, for all time i used to check webpage posts here in the early hours in the dawn, as i enjoy to find out more
and more.
I’ve been absent for some time, but now I remember why I used to love this site. Thanks , I will try and check back more frequently. How frequently you update your web site?
This post will assist the internet visitors for building up new weblog or even a
blog from start to end.
Excellent blog you have here but I was curious about if you knew of any user discussion forums
that cover the same topics discussed in this article? I’d really
love to be a part of group where I can get comments from
other knowledgeable individuals that share the same interest.
If you have any recommendations, please let me know.
Kudos!
If some one wishes to be updated with most up-to-date technologies afterward
he must be visit this web page and be up to date daily.
We are a gaggle of volunteers and opening a new scheme in our community.
Your site offered us with useful information to work on. You’ve performed
an impressive process and our entire community will likely be
grateful to you.
whoah this blog is fantastic i like studying your posts.
Keep up the great work! You already know, a lot of individuals are
looking around for this info, you can help them greatly.
Nice post. I learn something totally new and challenging on websites I stumbleupon every day.
It will always be exciting to read through content from other writers and practice something
from their web sites.
Great post. I was checking constantly this blog and I’m
impressed! Very useful information particularly the last part 🙂
I care for such information much. I was looking for this
certain information for a very long time. Thank you and
good luck.
Hey! Would you mind if I share your blog with my zynga group?
There’s a lot of folks that I think would really enjoy your content.
Please let me know. Thank you
Wonderful beat ! I wish to apprentice at the same time as you amend your site, how can i
subscribe for a blog web site? The account aided me a applicable deal.
I had been a little bit familiar of this your broadcast offered vivid transparent idea
Great information. Lucky me I recently found your blog by chance (stumbleupon).
I’ve saved as a favorite for later!
I like this web blog very much, Its a rattling nice spot to read and incur information.