【bzoj4570 scoi2016】妖怪

时间:2023-03-09 16:19:07
【bzoj4570 scoi2016】妖怪

题目描述

邱老师是妖怪爱好者,他有n只妖怪,每只妖怪有攻击力atk和防御力dnf两种属性。邱老师立志成为妖怪大师,于是他从真新镇出发,踏上未知的旅途,见识不同的风景。

环境对妖怪的战斗力有很大影响,在某种环境中,妖怪可以降低自己k*a点攻击力,提升k*b点防御力或者,提升自己k*a点攻击力,降低k*b点防御力,a,b属于正实数,k为任意实数,但是atk和dnf必须始终非负。

妖怪在环境(a,b)中的战斗力为妖怪在该种环境中能达到的最大攻击力和最大防御力之和。strength(a,b)=max(atk(a,b))+max(dnf(a,b))环境由a,b两个参数定义,a,b的含义见前文描述。

比如当前环境a=3,b=2,那么攻击力为6,防御力为2的妖怪,能达到的最大攻击力为9,最大防御力为6。所以该妖怪在a=3,b=2的环境下战斗力为15。

因此,在不同的环境,战斗力最强的妖怪可能发生变化。

作为一名优秀的妖怪训练师,邱老师想发掘每一只妖怪的最大潜力,他想知道在最为不利的情况下,他的n只妖怪能够达到的最强战斗力值,即存在一组正实数(a,b)使得n只妖怪在该环境下最强战斗力最低。

输入输出格式

输入格式:

第一行一个n,表示有n只妖怪。接下来n行,每行两个整数atk和dnf,表示妖怪的攻击力和防御力。1<=n<=10^6, 0<atk,dnf<=10^8

输出格式:

输出在最不利情况下最强妖怪的战斗力值,保留4位小数。

题意:
n只妖怪,有atk和dnf属性,每次可以选择一个环境a,b:可以使atk下降a*k,dnf上升b*k,或者相反,定义潜力为环境中最大atk和dnf的和,选择环境最小化最大的潜力;

题解:
①首先和a,b具体的值是无关的,只与a,b的比值有关:简化关系对于却定的a/b最大的潜力值是mx = A+B+A*b/a + B*a/b (令atk=A,dnf=B),      
令 k = -b/a,mx = A+B-(A*(1/k) + B*(k));后半部分对勾函数在k=sqrt(A/B)取得最小值;

②联想对于一个定点(x,y)斜率为k,那么其在x,y轴上的截距为:

x + y – x*k – y*(1/k),所以令x为B,y为A,就变成了截距的最大值最小。那么确定的k对n个点截距最大的一定在上凸包的右半部分上。

②枚举凸包上的点,如果k=sqrt(A/B)可选,则选,否则选择凸包的边界为k。

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAtQAAAE+CAYAAACtGoeJAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsMAAA7DAcdvqGQAACE8SURBVHhe7d1/jB7lgdjxx9is1+BAjMQFI0AsHJeksay0SO0pfzRnIAmElDhUsUiba0wVae1wSAEi2UYohgodtnoEJEKMGyosJW1anwoqLTlfAhzpP1VVnRTlXF0vLmAFdOccEjiOYdcGQ/eZH97X63d2Z3f23Xd+fD7Sq52ZtcH2zjvz3WefmVn2wZQAAAN09bP/LPn48i3/LfkI0CaCGoAlI6yBNhLUACw5YQ20iaAGYGiENdAGghqAoRPWQJMJagBqQ1gDTSSoAagdYQ00iaAGoLaENdAEghqA2hPWQJ0JagAaQ1gDdSSoAWgcYQ3UiaAGoLGENVAHghqAxhPWwDAJagBaQ1gDwyCoAWgdYQ0sJUENQGvlYR2Ja2BQBDUAnWDUGhgUQQ1ApwhrYLEJagA6SVgDi0VQA9BpwhqoSlADwBRhDSyUoAaAHsIamC9BDQB9CGugLEENALMQ1sBcBDUAlCCsgSKCGgDmQVgDMwlqAFgAYQ3kBDUAVCCsAUENAItAWEN3CWoAWETCGrpHUAPAAAhr6A5BDQADlId1JK6hnQQ1ACwRo9bQToIaAJaYsIZ2EdQAMCTCGtpBUAPAkAlraDZBDQA1IayhmQQ1ANSMsIZmEdQAUFPCGppBUANAzQlrqDdBDQANIayhngQ1ADSMsIZ6OSf7CACUsG/fvjA2Npa84vIwxJCOrxjWeVwDw2OEGgBKOHDgQNi6dWs4fPhwtiVVh9OoEWsYLkENACWsXbs2HDlyJFubduWVV4adO3eGzZs3Z1uGR1jDcAhqAJjDE088kYxOFxkdHQ179uypRVRHwhqWlqAGgD7yKR7R0aNHk9ds6hbVUe/8anENgyOoAaCPoikeExMTYdWqVdnameoY1Tmj1jA47vLBnOIoTbyafdmyZclrmFe2AyyVfjG9ZcuWJJp7PfTQQ9lSCJOTk7NODRmmGNLxFcO6d+QaqM4INXPqN0oTTyhxlAagreIodAzkXIzpOPocxcGFXDyN7tq1K+zYsSNZ7/11dWbEGhaPoGZWs12IY9cB2iyP5H6BPDOom0xYQ3WCmlkVzSGM6nSrKICl1KagzglrWDhBzax6Txr9mPoBdFEbgzonrGH+XJRIoTjdYy5xfqELFAHaI4Z0fMWwzuMamJ0RavqK0zzi3TzyC3JuvPHG5G4fuTgynX/OKDXQNW0eoZ7JiDXMzQg1fe3evfuMq9ufeeaZbCkV507n4q+LF+8A0D5GrGFuRqjpa+bFiHE3mTkic9ddd4VHH300WY+j1G+99VbyEaDtujRCPZMRazibEWr66n3E7m233ZYtnSk+zCD/XPwopgHaz4g1nM0INX3lo88bN24MP/rRj5JYLhqRiSPZl1xySbYG0H5dHqGeyYg1CGrmwQkEIOV4eDZhTZcJakpzAgFIOR4WE9Z0kaCmNCcQgJTj4dyENV0iqCnNCQQg5XhYXu+Fi+KathLUlOYEApByPFwYo9a0laCmNCcQgJTjYTXCmrYR1JTmBAKQcjxcHMKathDUlOYEApByPFxcwpqmE9SU5gQCkHI8HAxhTVMJakpzAgFIOR4OlrCmaQQ1pTmBAKQcD5eGsKYpBDWlOYEApBwPl5awpu4ENaU5gQCkHA+HQ1hTV4Ka0pxAAFKOh8MlrKkbQU1pTiAAKcfDehDW1IWgpjQnEICU42G9CGuGTVBTmhMIQMrxsJ6ENcMiqCnNCQQg5XhYb8KapSaoKc0JBCDleNgMeVhH4ppBEtSU5gQCkHI8bB6j1gySoKY0JxCAlONhcwlrBuGc7CMA0CEHDhwIGzZsCPv27cu2dEMM6fiKYd07JQSqMEJNaUZkAFJNPx7GmL7pppuytVRXj+tGrFkMgprSBDVAqunHw7GxsXD48OFsLf079P6dZurCMV9YU4UpHwDQMePj49lSCFu2bEk+xmguesXY7vdqE1NBqMIINaX1HjztNkCXOR6mZovqpv+7GLFmPgQ1pTmBAKQcD+fWltgW1pQhqCnNCQQg5XhYTRNjW1gzG0FNaU4gACnHw8Gpe2wLa/oR1JTmBAKQcjwcjqLYHsbXQFjTy10+AIBGiOHc7xVDu+iVi/fejrcLjNvix6oPtIkhHV8xrPO4pruMUFNa74HJbgN0meNhc/R+rXqNjo6GiYmJbK06I9bdJqgpzQkEIOV42Dy7du0KO3bsyNbOtJhfQ2HdTYKa0pxAAFKOh+2Sfz0HEdaRuG4/QU1pTiAAKcfDdhrU19WodfsJakpzAgFIOR623yC+xsK6vQQ1pTmBAKQcD7sl/3oLa4oIakpzAgFIOR5202J/3YV1ewhqSnMCAUg5HrKY+4Cwbj5BTWlOIAApx0N65fuDsO4uQU1pTiAAKcdD+lms/UJYN4+gpjQnEICU4yFzWYx9RFg3h6CmNCcQgJTjIfOR7y/Cur0ENaU5gQCkHA9ZiKr7jbCuL0FdU1W/mx0EJxCAlOMhVVXZh4R1/QjqGup9k+Xq8GVyAgFIOR6ymPL9ab77krCuD0FdU3WMaicQgJTjIYOw0P1KWA+foK6xflEdDetL5gQCkHI8ZNAWso8J6+ER1A1Ql7B2AgFIOR6ylOa7vwnrpSeoG2TYYe0EApByPGRY8n2vzH6Xh3UkrgdLUDdMUVRHg/5SOoEApBwP5+/ee+8NTzzxRLjwwgvDtm3bwpYtW7LPsBDz3QeNWg+WoG6oYYS1EwhAyvFw/i666KLw1ltvZWshXHnllWHnzp1h8+bN2RYWaj77o7AeDEHdcEVhPYgvqxMIQMrxcP527doVduzYka2lRkdHw8TERLbGYsj3zbn2S2G9uAR1SyxFWDuBAKQcDxdmcnIybN26Nezbty9Zj9M+9uzZkyyzuMruo8J6cQjqlhlkWDuBAKQGdTw8cOBA2L17d/ja175mKgSLpsz+KqyrEdQtNYiwFtQAqUEdD9euXRuOHDliKgQDk++7RfutsF4YQd1iRVEdLeTLLqgBUot9PIwj03EqxOHDh7MtjrMM1lz7sLCeH0HdAUVhPd8vvaAGSC328XBsbOyMmI4cZ1kqs+3Pwrqcc7KPtFh8c/Q7MMc3UFFsA7B0xsfHs6WUezSzlPJOiK+ZbRBDOr5iWOdxzdmMUHdQUUTPtSv0/j67DdBljoe0XdE+bsS6PyPUHRTfGP1OAPHNUxTbAMBgxbn0GzZsOH1bwWHKWyG+8j6ILyPW/Rmh7rjZAnrmrtH7a+02QJc5HjIITbjLS77v5/u9EeuUEeqOi2+IopPBbLENACyeODodYzqKD8C5//77k+W6ybshNkJ8vfLF/27EeooRas5QFNH5mydntwG6zPGQxdbvTi87d+6sbVj36n0/XPVfv5B87NqItRFqzhBPDP1ODkWhzZTnt4U3L78mHH8+W6+FF8PxqT/Tm/e8mK0DUGcbN27MlqY98MADYdeuXdlafeXtEF9xxDq+8hHr+IrfLNRhXvggGaFmVrONWDPllSfDsU/vDu/F5U17w0UPX5dsHroY+bc/nSyuuO8n4YLxsWQZWBxGqFlscZpHfLjPzPBs6lMzuzZqLag77o0TL4WDv7k3TJx6PdtyplXLLwt/8q2/Cj/+wfFsy5m6vfvEUeDxcHJqqZbRejr214XzfvZMGL0q2w5UJqgZlDgivWPHjmwt9dBDD4Xt27dna80x8+/S5rAW1B33wq+vDSfefyNbK/bRD20Pv/uhO7K1s3VxNzq190vhNw8erNfI9Ayn/4zrt4ULn/t6WJ5tB6oR1AzSzBBt6ih1lP9d4sOK9uzZk2zLL15sU1gL6o778d9dkS3N7pxlK8MXr3w5nDxRvLt0a1fKR6frPvo7PYo+8tShsPqGdCtQjaBm0OIUkDVr1iQfozbuZ20Kaxclctrn1/7qjNeNlxwKl666Jflc/Ngb0/3e2PEE03uSabXn/zyJ1LD+5nBuradSXBdW3bcuWTr5Zy5QBGiKOCod7/IRtfVR9DGk4yu/eLHJBDWF4qj0Jz/83XD9R/4yrL/w4WzrtBjVXQ3rUy//Mvm44pbr+0yjyO6wMeMuGyfvybZd/qUw+Uq2cT6yu4mc/fun/3/H9r6abZu2/OrfSxf+7yvhVLoEQAPEedPxPJtPlWirNoS1oGZOK8+5OFvqr4thfeqXB7Olfq4Lq5+6NV3c/1gav688GSb3p5tW3PedhU0RueFzYSRZOBhO/nQ6nE/tfSwdLQ/rwshn+lwYedU1YUX8+ItDghqA2mpyWAvqRpoekex/7+NXw+TNxSOWg9IvqqMujFif5YbdYfWmuHAwvHPntnD8zuzWeuu3hfMXfDeQ6ekb7z37QhbHr4Z3n83ivvbTTwBgbk0Ma0HdGDGi8x/1j4UV65ONp8XpBEsZz0WKRqujrkX1yMM/CefFr9Mvng4nfxG3rAvnPVbtThvLP3NzNtr8XHg3Gfl+IftvT/3/7prjv73+Gnf5AKAxmhTWgroh0h/rHwzvfLo3nNeFFS9nT+nbH8J7Dz6R/eh/+No+DWT572Ujxb+c7ZuYsTB6Vzb1Y8qCp3r0uur6MJJ8MzW1Lzz+Yjj10+fSke9waxgpuoPHK4eyXwMAzdOEsBbUDbF8/Jlw0c+2JaOT7z04Ht5JRiWnourB9Gl4yb2QX9udzbGtj7aG9emR4v3Z3T76ejEcz55WGL334GcX4fHkY+HcW9KYj/Oz386ne2zK51ef7eSfZU9M7HsBJQA0Q53Dul1BvcC7IAzP9J+r1N0grvp6uOC1Q9nc3Fy8D/KhEg8WmZ5X/ebl25Z8JLt1YX16pPjpcLJwHvv0UxTzr9nJ26v/2y8fv/P0xYnv5dM9bir4+p++GLLggkWglQ4cOBA2bNhw1mOsoQ3qGNbtCuqF3gVhDtOBO8vr5icXcAeF+d0NIv9zxOkd09JpILPfii3G3WezUe1bw+ohjmT3i+qoeWE9PZ2jXySf2nt3+u+dXYQ48vDe7N/86XC855unKD7NMN+Pyo1gXxdGer+pmvp/rCqY7nHy8exiyE13evQ4dMjtt98eXnrppbB169ZsC7RPncK6ZVM+GngXhJJ3g4jRlYf0ivv2phe7JaPTeajFsO43+lmfmM4VjVZHjYrq01+7qUju/YZq6puit+PjvuPX5/RFiL3fPI1X/knJyE09c7MLpnJM7zNTX/eaPhod2iaODI+NjZ0eJIjLwxglPnr0aPIxf8oetFkdwnrZVNj0L5ummoqZY5+OUZo9Ejrk63V+9HJv9EbZn70w/uNUkdkeJz3zv5eKUw8umHHLtt5Hj8enI86mN3YXc7cpiuhm7Jo9/9ZxHvuCwjX7ek59E3XhcyXvAhKnNyXzs/vvKzGmf5NHfa0fjQ7NVHQ8jAF9+PDhbC0Vn3g3MTGRrS2NXbt2hR07diRP2Gv7Q0FgpjyqY2QvlfZdlLiQuyAM3QDuBnHaujCyKRu1f/DuWaaFDE88GfWL53yEp96mvnbPHQoXvVZmHnuB7DHmc972bsrp6SH5xY4FUzmSi1jjn+k1MQ1LaXx8PFuatnnz5mxp6XTlCXvQz8wR66UYtW7fCPWU3tG5FesPphduLXj0cClMjzjnqo2m94yaJqOe14d3C0ZR6zBCPVOzR6yBLliq4yGwOAY9at3K2+bN6y4IQxfjdzB3g0h87KqwvHcEfP/4Ity6bbCKTk7NGLEGAOpm5qj1YmtlUM/nLgjDNp+7QVRy+gK6RYz1AYpRLawBgMU0qLBuaVDHEem574IwdEtwN4heI3ekD4ZZ9FgfoLnCGgBgvhY7rFs5hzoxx10QSNVxDvVsiiK6rbsxUE91OB4CiyeP6hjZC9G6oJ6+IDFT64sRh69pQZ0T1sAwCWpop4WGdXtHqCmlqUGdE9bAMAhqaLf5hrWg7rA3TrwU/veb/ypba2ZQR0VRHdm9gUEQ1NANZcNaUHfYC7++Npx4/41srblBnSsKa7s4sNgENXTLXGEtqDusd7rHFed/Nay74I+ztf6acgIR1sCgCWropqKwFtQdNp/501HTTiD9wvraDaPh3/6nfxgmTr0eVi2/LFyz+q5w2Xlfzj4LUI6ghm6bGdaCuqMO/faRcOj4I9laO4M61/vn/uHPLw1rfufMu5ILa2C+BDULdeDAgbB169ZkeefOnWHz5s3JMs2Uh7Wg7qBfvf3DcPDYvdlaCJeuuiV88sPfzdaKNfkEEv/scXT63/yHi7MtZzpn2cpw4yWHsjWA2QlqFmpsbCwcPnw4WR4dHQ179uwR1S3Q2iclUqx3ZPrilX8Q1l/4cLbWXvGEt/tH/yBbO9v7H5zIlgAYtjiKu2HDhrBv375sS3ts3LgxWwphcnLy9Gg1zWaEuoN6507HUdk4OltG00dkDhy5ZtZwfuSbb4af/ufj2RpAMSPUg7V27dpw5MiRZAR3YmIi29oOMaLXrFmTfMzZh5rPCHXH9N4mLyob020Q50nP5o7da5KTZO+JEoCld/To0eRjb3S2RfwmIc6dpl0Edce8cvx72VIIF5z7iWypG65e/Y1Zv4F4fv/b2VI6+iSsAYYjD84tW7YkH9tm+/bt4aGHHkqW2/p37BpTPjqm92Eu1675fvjI6OeS5TLa8CPOl6e+ofib3+7K1lL5PbhnC2hvE6BXG46HwOIR1B0SQzoGda7MrfJ6deUEIqyBuQhqoJcpHx3S5eke8xFPjkUnyNliGwDoJiPUHfHGiZfCz4/+UXj3/WPZlmllH2zS1RGZooj21oHuMkIN9BLUHfEXf/+p5HHbRco82KTrJxBhDeQENdDLlI+OuOK8r2ZL/cX7M8cL9igWT5r9TpzxxFoU2wBA+xmh7ri/PvZAePXtf58szzVKbURm2mwB7S0F7ed4CPQyQt1xH/3Q9mzJ47fnI55Ai06iRqsBoFsEdcd16UmJg1AU1jGqhTUAdIOghkUgrAGguwQ1LCJhDQDdI6hhAPpFdSSsAaB9BDUMSNFodSSqAaA9BDUMmGkgANBughqWiLAGgHYS1LDEhDUAtIughiHpF9WRsAaAZhHUMERFo9WRsAaAZhDUUANzhTUAUF+CGmqkKKyNVgNAfQlqqCFhDQDNIaihxoQ1ANSfoIYG6BfVkbAGgOET1Jzh9Xf+NFuibopGqyNRDQDDI6gJ5yxbmS2FcPDYvdkSdWUaCADDdODAgTA2Npa8nnjiiWxrtwlqwjWr78qWQnj/gxPZEnUnrAEYhq1bt4bDhw8nr7h8//33Z5/pLkFNuHr1N7KllGkfzSKsAVhK4+Pj2VLqgQceSEar9+3bl23pHkFNYua0D1HdPP2iOhLWgxd//LlhwwY/+gQ6Yfv27WFiYiLceOON2ZZwerS6qwQ1iZnTPmJU/8Xffyp5ievmKBqtjkT14MSTyEsvvZR8NKcQ6ILR0dHwzDPPhM2bN2dbQpicnAy7du3K1rpFUJOI0z4++qHt2Voa1ROnXk9eLlRsHtNAltbGjRuzpelRGmENtF2M6qeeeip885vfzLaEsHPnzvDxj3+8c9M/lk2ddPsPZ9FJLx//Xvib35793eXn1/4qCbFrN4yGL//RBeFf3vjdcNl5X84+S90VRbS3/+KIozIxovudQOLJxQU77dP7nvI+ouviMXDNmjXJx1yM7TgtpCsE9Tx0ZWQvBvPmey/M1kL48Q+Oh8e3vZUs//Dnl4Y1v7M8nDzxQfjS2OvJNqCcuhxu/ZQCWApdSkxBPQ9OQiE897eXZ0sh3Hzpa9kSdXfDpvPDv7jngmT5Pz58LDy//+1kmaX10EMPJRfzDJtjGbAUupSY5lCzYDHSqL/P/+HqcNejF4WPXL4ied2xe032GZbajh07kpjt+u2lANrGCDWlxRB45tXLwsjKdHQr3mrvxksOJcvUT7w7y6HjjyQXlva64vyvhnUX/HG2Vjxa6dAwf0ePHk3ux/roo49mW4p1bX5h2/S+b7xXYFpX3xuCmtLim2Tm/OoyVi2/LFx9/jeSkGPw3jjxUjj4m3vPCukofgPUe8/xXsJ6YeJIc4zoeHeP+diyZUvYs2dPtkbTCGroT1DDHPI3Se8o9XwI66Xxwq+vDSfefyNbmzZzZLqIsJ5bfJBLvKvHbBEdH3gQ79EaR6JpH0EN/QlqmEP+JlnIKHUZMbgvGf1cuGr1N8LKcy7OtjKX2UakL111S1h/4cOFo9KzEdb9xZj+yle+kkzv6OfKK69MbpXX+7AD2kdQQ3+CGuawkDdJ/tTFhTxtMQZ2fIKj+12fabaA7hVj+pMf/m62tjBFUR119dARLyicOTJ92223JQ83MBrdHYIaztRv+luX3huCmtKqnEAWGtZxZDVOU+h6VBddYFikysh0P0Vh3cXDR3ysbrxbR2QedHcJakjNNgWuS+8NQU1pgz6B/Hryz6ei8dFw7N3/k21JdTeqXwzHLx8Pr9z3++H1W36WbStWdo50FcIaUoIaUmvXrg1HjhzJ1qZ1bcBBUFPaUp5AZj4CPUZ1fou+slMeijRhKkn8O/7Vq18LkxcW/zsvRUAXEdZ0naCG1KpVq04/crzL098ENaUt9QlkZlR/fu2vkqkPf/3bB8K77x/LtnbHxSv/SfjEv/55mPzLEFbc95NwwfhY9pnhEdZ0laCGVD4NrutT4AQ1pQ3jBPLjv7siW0rnBf/txLPZWrekc6LvDCe/8IXwzi/qE9RRUVRHDi+0laAGeglqShvGCeTAkWuSCxr7WciUh5mj3nV35t/x1TB582drF9S5orB2iKGNBDXQS1BT2jBOIP0C+OKVfxCuXfP98N631oXj++OWdeG8nz0TRq9KPj18z28Lb97+9NTCzD9XepHhyaml4iDOo7nf36lfUE9vC+HWsPq13WEkLg6RsKYLBDXQ65zsI9TS1au/kS1N+8TR74dzXv1BmExiOsbldxYU0yfvuSa8efkcr5ufDKeyX1/aDZ/LovZgOPnTV5Ol6NTex5KYjqE98pn+o8un9t6dBXOZv1P9YjqKcdEvMGKAFMU2ADSZoKb2eu+l/JGnl4fJO78djt+5O7wXN6zfFs6v2dSHEK4Lq+5blyy99+wLWZC/Gt599mCyFNbfHM7tG8svhokH46+5NYzO+XeqZ0z3EtYAdIUpH5Q2rB9x5tM+rjj/i+F3v3Igi8ioZlM9er3yZDj26Rj92Z8x5OshjDx1KKy+If1lvU7t/VL4zVRQF33+zIieVsf51DPNFtAOQTTRsI6HQD0Zoab24rSPeMu8dRc8FkbvujXbuvCpHkviquvDyPq4cDC88/iL4dRPn0tH1MOtYaRfLE8F+NtxdHr9trCqb0zPtC6MbMpGwR+8O0y+kizWVgyOougwYg1A0wlqGuTFcDy52C/13oOfDcefz1ZqZyyce0savGH/Y+HtfLrHpnx+9ZlOPp6NXt/19bA83TS79TeHVQ9/J5zXE+1NMFdYA0ATCWoaIk53mL5DxupN6daTt2/LLvSrn+Xjd56+OPG9bJrGyE3XpQu9nt+W3q1k096CqR59fOyqqfAemx6x3z9e428uzlYU1karAWgiQU0j5He/yC9CHHl4bxarT4fj99R1dPa6MJKFf6LvdI6pbxQeyW6xd0ef2J7LDbsb8c1FEWENQBsIauovn18co/OxfErEdWH1U9Ojs8f2Tt+erk5GbuqZ833L9WdP53j+ifQbhU13Lng++Mgd28KKZKnO31zMTlgD0GTu8kFpvWFjtymp8CEvqeTOHr+8M1z08AJGp1tqtoC231EXjodAL0FNaU4g5eW3wDtt017RPE9FYW3fow4cD4FegprSnEAYBmFNHTkeAr3MoQZqLcZKv2CJQVMU2wCwlAQ10AizhTUADJOgBhpFVANQN4IaaJyi0WoAGAZBDTRWHtbiGoBhEtQAAFCBoAYAgAoENQAAVCCoAQCgAkENAAAVCGoAAKhAUAMAQAWCGqihV8PkzdeENy+/Jhzb+2q2DQDqSVADAEAFghoAACoQ1AAAUIGgBhpiel71m5dvCyezrQAwbIIaaIAY058N7/wiLt8aVr+2O4wk22d34k+fDr/d9NXkIwAMiqAGam7+MR0D+uinNoS3794W3v2f/yu8s+Pb4YMTJ7LPFnv3pf+R/L74mvzBj7KtADC7ZR9MyZZhVsuWLcuWQrDbMFi9ET1txX0/CReMj2VrZ4shPfHIY+H9117PtqRW3vKFcP7jj2RrZ4oRPfm9fxdGvnzrWb/3nMsvC6vuujOsnPoc9HI8BHoJakpzAmHp9Ab1ujCyKYST+w8my+f97JkwelXcPq0opKMY0+d9Z1dYtnJltuVMR//Rp8L7b7yRfH50Kp4ndv1J9plU3L7m/8X/N0xzPAR6mfIB1Nv6m8Oqh78TzlsfVw6Gdx5/Mdkc5VM04tSOfqPSMYTjyHRRTEcxpqM4JWTVHePJ71m56Z8n26IyU0UA6DZBDdTbx64Ky8NYGL0rm3axfzwcfz5dfPvu7QsO6SLx95z/8K5sDQDmJqiBZrhhd1i9KV08eXt627wPjh1LN2TinOflv/+PFxTSALBQghpojJE7toUVydLT4fg9L4aVf/iVZC0XR6vfuffb7tIBwJJyUSKluQiHuonzm9+5d2c4sf+/ZFvOtGr7t5J50bOJD4rJXfTaoWypeDtEjodALyPUQGPl851j8M68mDCafOSxBT3UJb9QEQDKENRAK+RxHcM6n0MdR7DjHUDiFJD5hHUM8dyKT3w8WwKA/gQ10CoxpuP9pHslc6t3fDtbm12ce907/3rmfwsAZhLUQOvEedNx/nSvsveT7h2dPvcP/mkY+dxnsjUA6E9QA60UozrOrc7DenTGHUGK9M6fXv3k97IlACjmLh+U5qp22qj3bh4zubsHRRwPgV5GqIFO8xAYAKoS1ECnFV10WHaKCACY8kFpfsQJkHI8BHoZoQYAgAoENQAAVCCoAQCgAkENAAAVCGoAAKhAUAMAQAWCGgAAKhDUAABQgaAGAIAKBDUAAFQgqAEAoAJBDQAAFQhqAACoQFADAEAFghoAACoQ1AAAUIGgBgCACgQ1AABUIKgBAKACQQ0AABUIagAAqEBQAwBABYIaAAAqENQAAFCBoAYAgAoENQAAVCCoAQCgAkENAAAVCGoAAKhAUAMAQAWCGgAAKhDUAABQgaAGAIAKBDUAAFQgqAEAoAJBDQAAFQhqAACoQFADAEAFghoAACoQ1AAAUIGgBoB5+uCDD06/AAQ1AABUIKgBAKACQQ0AABUIagAAqGDZB66oAACABTNCDQAAFQhqAACoQFADAEAFghoAACoQ1AAAUIGgBgCACgQ1AABUIKgBAKACQQ0AABUIagAAqEBQAwBABYIaAAAqENQAAFCBoAYAgAoENQAAVCCoAQCgAkENAAAVCGoAAKhAUAMAQAWCGgAAKhDUAABQgaAGAIAKBDUAACxYCP8fVyeSPhjCk1IAAAAASUVORK5CYII=" alt="" />

算很隐蔽了吧。

 #include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int N = ;
double inf = 1e15;
int n,m;
struct point{
int x,y;
point(int x = ,int y = ):x(x),y(y){}
bool operator < (const point &a)const{return (x==a.x)?y<a.y:x<a.x;}
point operator - (const point &a){return point(x-a.x,y-a.y);}
}p[N],ch[N];
char gc(){
static char *p1,*p2,s[];
if(p1==p2) p2=(p1=s)+fread(s,,,stdin);
return(p1==p2)?EOF:*p1++;
}
int rd(){
int x = ,f = ; char c = gc();
while(c<''||c>'') {if(f=='-') f = -; c = gc();}
while(c>=''&&c<='') x = x * + c -'',c = gc();
return x * f;
}
const double eps = 1e-;
int dcmp(double x){return (fabs(x)<eps)?:x<?-:;}
ll cross(point a,point b){return 1ll*a.x*b.y - 1ll*b.x*a.y;}
void convexhull(){
sort(p+,p+n+);
for(int i = n;i>=;i--){
while(m>&&dcmp(cross(ch[m]-ch[m-],p[i]-ch[m])<=)) m--;
ch[++m] = p[i];
}
}
double K(point a,point b){return 1.0*(a.y-b.y)/(a.x-b.x);}
double calc(double k,point a){return a.x+a.y-/k*a.y-k*a.x;}
int main()
{ //freopen("bzoj4570.in","r",stdin);
//freopen("bzoj4570.out","w",stdout);
n = rd();
for(int i = ,A,B;i <= n;i++) {
A = rd(); B = rd();
p[i] = point(B,A);
}
convexhull();
double ans = inf;
for(int i = ;i <= m;i++){
double k1 = (i!=m)?K(ch[i],ch[i+]):;
double k2 = (i!=)?K(ch[i],ch[i-]):-inf;
double k = -sqrt(1.0 * ch[i].y / ch[i].x);
if(dcmp(k1-k)>=&&dcmp(k-k2)>=)
ans = min(ans,calc(k,ch[i]));
if(i!=m&&ch[i+].y<ch[i].y) break;
if(i!=m) ans = min(ans,calc(k1,ch[i]));
}
printf("%.4lf\n",ans);
return ;
}//by tkys_Austin;