happy解題報告初步分析

Happy解題報設這n個點的坐標為(x1,y1x2,y2xnyn)，y1y2yn2、所有的yi(1in)互不相(xi,(xi,(l<=xi)且(r>= 若不然，不妨設lxi，r<xi（l>xi,r>xi的情況類似可證y0=0，那同時矩形不能包含任何產(chǎn)奶點，設上邊界為y=yj，那么：l=max{xp,0} （i<p<j, xp<=xi）r=min{xp, （i<p< xp>=fori:=1tondobeginl0;rw;forj:=i+1tondoify[j]y[i*rl)>最優(yōu)值then更新ifx[j]<=x[i]thenlmax{l,ifx[j]>=x[i]thenrmin{r,x[j]}if(h–y[i])*(r–l)>最優(yōu)值then更 {上邊界與牛場上邊界重合輸出最2、所有的yi(1in)互不相首先考慮yi可能相同的情況。取下邊界為y=yi(xi,(xi,(xi+1,設左邊界為l，右邊界為r(l,yi)與(r,yi)之間的線段上，至少有一個產(chǎn)奶點。fori:=1tondobeginl0;rw;forj:=i+1tonify[j]≠y[i]thenify[jy[i*rl)>最優(yōu)值then更新ifx[j]<=x[i]thenlmax{l,ifx[j]>=x[i]thenrmin{r,x[j]}ifhy[i*rl)>最優(yōu)值then更輸出最整個算法的時間復雜度是O(n2)fin='happy.in';fout='happy.out';maxn=5100;n:x,y:array[0..maxn]ofinteger;w,h:integer;result:i:integer;readln(w,h);fori:=1tondoreadln(x[i],y[i]);procedureprint;輸出}assign(output,fout);rewrite(output);proceduresort; i:procedureswap(varx,y:integer);t:integer;t:=x;x:=y;y:=t;proceduresift(s,t:i,j:integer;i:=s;j:=i+i;whilej<=tdobeginif(j<t)and(y[j+1]>y[j])theninc(j);ify[i]>=y[j]thenbreakelsebeginswap(y[i],y[j]);swap(x[i],x[j]);i:=j;j:=i+i;fori:=nshr1downto1dosift(i,n);fori:=ndownto2dobeginswap(x[1],x[i]);swap(y[1],y[i]);sift(1,i-1)procedureinitresult; maxw:longint;p,i,l,t:d:array[0..maxn]ofinteger;fillchar(d,sizeof(d),result:=l:=2;d[1]:=0;d[2]:=w;maxw:=w;fort:=1tondobeginifmaxw*y[t]>resultthenresult:=maxw*y[t];p:=1;whiled[p]<x[t]nc(p);fori:=l+1downtop+1dod[i]:=d[i-1];d[p]:=x[t];inc(l);maxw:=fori:=ldownto2fd[i]-d[i-1]>maxwthenmaxw:=d[i]-d[i-1];ifmaxw*h>resultthenresult:=maxw*h;proceduremain; l,r:longint;s,i,j:integer;fori:=1tondol:=0;r:=w;s:=i+while(s<=n)and(y[s]=y[i])nc(s);forj:=stondobeginif(r-l)*(y[j]-y[i])>resultthenresult:=(r-l)*(y[j]-y[i]);if(x[j]<=x[i])and(x[j]>l)thenl:=