中国建设银行龙网站首页,福彩网网站建设方案,个体户可以做网站吗,成都网站建设上云Description Input Output Sample Input 3 1 1 1 2 2 2 Sample Output 8.0000 Data Constraint 题解 我还挺喜欢数学的呢 这题一眼看上去不会#xff0c;化化式子没想到未知数竟然是一个反比例一次函数的样子。 长这样#xff1a;axbx\frac a xbxxabx 当时心态就没了。 原来… Description Input Output Sample Input 3 1 1 1 2 2 2 Sample Output 8.0000 Data Constraint 题解 我还挺喜欢数学的呢 这题一眼看上去不会化化式子没想到未知数竟然是一个反比例一次函数的样子。 长这样axbx\frac a xbxxabx 当时心态就没了。 原来这玩意是一个在高中叫做双勾函数或对勾函数或耐克函数 很好于是我们就看看这个玩意长什么样—— 既然是长这个样子那么应该就有一个顶点最小点。 利用均值不等式可以得到——(aba,2ab)(\frac{\sqrt{ab}}a,2\sqrt{ab})(aab,2ab) 由于图中有很多很多的双勾函数那么其中必然有一些线没有用的。 我们考虑删去这些没有用的 怎么删 首先我们对于任意两点——满足ailt;aj且yilt;yj答案a_ilt;a_j且y_ilt;y_j答案aiaj且yiyj答案 那么aibiai∗xbixlt;ajbjaj∗xbjxa_ib_ia_i*x\frac{b_i}{x}lt;a_jb_ja_j*x\frac{b_j}{x}aibiai∗xxbiajbjaj∗xxbj 化一波式子得到xgt;bi−bjaj−aixgt;\frac{b_i-b_j}{a_j-a_i}xaj−aibi−bj 设c[i,j]bi−bjaj−aic[i,j]\frac{b_i-b_j}{a_j-a_i}c[i,j]aj−aibi−bj 则我们对于一个c[i,j]gt;c[j,k]c[i,j]gt;c[j,k]c[i,j]c[j,k]那么j这个点就是没有用的。 所以说我们就得到一个序列ddd序列满足c[di−1,di]lt;c[di,di1]c[d_{i-1},d_i]lt;c[d_i,d_{i1}]c[di−1,di]c[di,di1] 这个东东是递增的。 那么我们发现当xxx在c[di−1,di]c[d_{i-1},d_i]c[di−1,di]到c[di,di1]c[d_i,d_{i1}]c[di,di1]这段区间内时did_idi的函数值是最大的。 因此我们在did_idi的函数上判断这段区间的最小值即可。 怎么判断可能有三种情况 1、在顶点左边。 2、在顶点右边。 3、横跨顶点。 O(n)O(n)O(n)求即可。 代码 vari,j,k,l,n,m,now:longint;a,b,d:array[0..1000003] of longint;op,oq,x,y,ans,aa,bb:extended;
function min(x,y:extended):extended;
beginif xy then exit(x);exit(y);
end;
procedure qsort(l,r:longint);
vari,j,m,m1:longint;
begini:l;j:r;m:a[(lr) div 2];m1:b[(lr) div 2];repeatwhile (a[i]m) or ((a[i]m) and (b[i]m1)) do inc(i);while (a[j]m) or ((a[j]m) and (b[j]m1)) do dec(j);if ij thenbegina[0]:a[i];a[i]:a[j];a[j]:a[0];b[0]:b[i];b[i]:b[j];b[j]:b[0];inc(i);dec(j);end;until ij;if lj then qsort(l,j);if ri then qsort(i,r);
end;
function pd(i:longint):boolean;
varx,y,op,oq:extended;
beginx:b[d[now]]-b[d[now-1]];y:a[d[now-1]]-a[d[now]];op:x/y;x:b[i]-b[d[now]];y:a[d[now]]-a[i];oq:x/y;if opoq then exit(true);exit(false);
end;
begin//assign(input,monster.in);reset(input);readln(n);for i:1 to n dobeginread(a[i],b[i]);end;qsort(1,n);now:1;d[1]:1;for i:2 to n dobeginif a[i]a[1] thenbegininc(now);d[now]:i;j:i;break;end;end;for i:j1 to n dobeginif a[i]a[d[now]] thenbeginwhile (now2) and (pd(i)) do dec(now);inc(now);d[now]:i;end;end;ans:maxlongint;for i:2 to now-1 dobeginx:b[d[i]]-b[d[i-1]];y:a[d[i-1]]-a[d[i]];op:x/y;x:b[d[i1]]-b[d[i]];y:a[d[i]]-a[d[i1]];oq:x/y;aa:a[d[i]];bb:b[d[i]];if opsqrt(aa*bb)/aa then ans:min(ans,aa*opbb/opaabb);if oqsqrt(aa*bb)/aa then ans:min(ans,aa*oqbb/oqaabb);if (opsqrt(aa*bb)/aa) and (oqsqrt(aa*bb)/aa) then ans:min(ans,2*sqrt(aa*bb)aabb);end;x:b[d[now]]-b[d[now-1]];y:a[d[now-1]]-a[d[now]];aa:a[d[now]];bb:b[d[now]];op:x/y;if opsqrt(aa*bb)/aa then ans:min(ans,aa*opbb/opaabb)else ans:min(ans,2*sqrt(aa*bb)aabb);writeln(ans:0:4);
end.转载于:https://www.cnblogs.com/RainbowCrown/p/11148359.html
