happy解题报告初步分析

Happy解题报设这n个点的坐标为(x1,y1x2,y2xnyn)，y1y2yn2、所有的yi(1in)互不相(xi,(xi,(l<=xi)且(r>= 若不然，不妨设lxi，r<xi（l>xi,r>xi的情况类似可证y0=0，那同时矩形不能包含任何产奶点，设上边界为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)>最优值then更新ifx[j]<=x[i]thenlmax{l,ifx[j]>=x[i]thenrmin{r,x[j]}if(h–y[i])*(r–l)>最优值then更 {上边界与牛场上边界重合输出最2、所有的yi(1in)互不相首先考虑yi可能相同的情况。取下边界为y=yi(xi,(xi,(xi+1,设左边界为l，右边界为r(l,yi)与(r,yi)之间的线段上，至少有一个产奶点。fori:=1tondobeginl0;rw;forj:=i+1tonify[j]≠y[i]thenify[jy[i*rl)>最优值then更新ifx[j]<=x[i]thenlmax{l,ifx[j]>=x[i]thenrmin{r,x[j]}ifhy[i*rl)>最优值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:=