Hướng dẫn giải của Xây dựng lâu đài
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const fi=''; maxn=5010; type ar=array[1..maxn] of longint; var n,nx,ny:longint; smax,smin,re,cmax,cmin,oo:qword; a,b,e,d,x,y:ar; f,g,h:array[1..maxn,1..maxn] of integer; procedure rf; var i:longint; begin read(n); for i:=1 to n do begin read(a[i],b[i]); x[i]:=a[i]; y[i]:=b[i]; d[i]:=i; e[i]:=i; end; end; procedure sort(var x,d:ar;l,r:longint); var i,j,t,u,v:longint; begin i:=l; j:=r; t:=x[(i+j) shr 1]; u:=d[(i+j) shr 1]; repeat while (x[i]<t) or ((x[i]=t) and (d[i]<u)) do i:=i+1; while (x[j]>t) or ((x[j]=t) and (d[j]>u)) do j:=j-1; if i<=j then begin v:=x[i]; x[i]:=x[j]; x[j]:=v; v:=d[i]; d[i]:=d[j]; d[j]:=v; i:=i+1; j:=j-1; end; until i>j; if i<r then sort(x,d,i,r); if l<j then sort(x,d,l,j); end; procedure edit(var x,d,a:ar;var nx:longint); var i:longint; begin nx:=1; a[d[1]]:=1; for i:=2 to n do begin if x[i]>x[nx] then begin inc(nx); x[nx]:=x[i]; end; a[d[i]]:=nx; end; end; procedure pr; var i,j,last:longint; s,ss:qword; begin oo:=2000000000; oo:=oo*oo*4; last:=1; smin:=oo; for i:=2 to n do if a[i]=a[last] then begin for j:=last to i-1 do begin if f[b[j],b[i]]>0 then begin re:=re+f[b[j],b[i]]; s:=y[b[i]]-y[b[j]]; ss:=s*(x[a[i]]-x[h[b[j],b[i]]]); s:=s*(x[a[i]]-x[g[b[j],b[i]]]); if s=smax then inc(cmax); if s>smax then begin smax:=s; cmax:=1; end; if ss=smin then inc(cmin); if ss<smin then begin smin:=ss; cmin:=1; end; end else g[b[j],b[i]]:=a[i]; inc(f[b[j],b[i]]); h[b[j],b[i]]:=a[i]; end; end else last:=i; writeln(re); if re>0 then begin writeln(smax,' ',cmax); writeln(smin,' ',cmin); end; end; begin assign(input,fi); reset(input); rf; sort(x,d,1,n); edit(x,d,a,nx); sort(y,e,1,n); edit(y,e,b,ny); sort(a,b,1,n); pr; close(input); end.
Code mẫu của ladpro98
#include <bits/stdc++.h> #define ii pair<int, int> #define X first #define Y second const int N = 5005; using namespace std; ii X[N], Y[N], a[N]; bool chk[N][N]; int vX[N], vY[N]; int n, cnt; unsigned long long SMAX, CMAX, SMIN, CMIN, S; int main() { scanf("%d", &n); int i, j, x, y, d; for(i = 1; i <= n; i++) { scanf("%d %d", &x, &y); X[i] = ii(x, i); Y[i] = ii(y, i); } sort(X + 1, X + 1 + n); sort(Y + 1, Y + 1 + n); X[0].X = X[1].X - 1; Y[0].X = Y[1].X - 1; d = 0; for(i = 1; i <= n; i++) { if (X[i].X != X[i - 1].X) { d++; vX[d] = X[i].X; } a[X[i].Y].X = d; } d = 0; for(i = 1; i <= n; i++) { if (Y[i].X != Y[i - 1].X) { d++; vY[d] = Y[i].X; } a[Y[i].Y].Y = d; } for(i = 1; i <= n; i++) chk[a[i].X][a[i].Y] = true; SMAX = 0; SMIN = -1; for(i = 1; i < n; i++) for(j = i + 1; j <= n; j++) if (a[i].X != a[j].X && a[i].Y != a[j].Y && chk[a[i].X][a[j].Y] && chk[a[j].X][a[i].Y]) { cnt++; S = (unsigned long long)abs(vX[a[i].X] - vX[a[j].X]) * abs(vY[a[i].Y] - vY[a[j].Y]); if (SMAX < S) {SMAX = S; CMAX = 1;} else if (SMAX == S) CMAX++; if (SMIN > S || SMIN == -1) {SMIN = S; CMIN = 1;} else if (SMIN == S) CMIN++; } cout << cnt / 2 << endl; if (cnt > 0) { cout << SMAX << " " << CMAX / 2 << endl; cout << SMIN << " " << CMIN / 2; } return 0; }
Code mẫu của RR
//Written by RR {$R-,Q-} uses math; const FINP=''; FOUT=''; MAXN=5001; oo=1000000000000000; type list=^node; node=record u:longint; next:list; end; var f1,f2:text; n:longint; ds:array[1..MAXN] of list; c,ind,x,y:array[1..MAXN] of longint; count,smax,smin,cmax,cmin:int64; procedure openF; inline; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; inline; begin close(f1); close(f2); end; procedure inp; inline; var i:longint; begin read(f1,n); for i:=1 to n do read(f1,x[i],y[i]); for i:=1 to n do c[i]:=x[i]; end; procedure swap(var a,b:longint); inline; var temp:longint; begin temp:=a; a:=b; b:=temp; end; var mid:longint; procedure sortC(l,r:longint); inline; var i,j:longint; begin i:=l; j:=r; mid:=c[l+random(r-l+1)]; repeat while c[i]<mid do inc(i); while c[j]>mid do dec(j); if i<=j then begin swap(c[i],c[j]); inc(i); dec(j); end; until i>j; if i<r then sortC(i,r); if l<j then sortC(l,j); end; procedure sortY(l,r:longint); inline; var i,j:longint; begin i:=l; j:=r; mid:=y[l+random(r-l+1)]; repeat while y[i]>mid do inc(i); while y[j]<mid do dec(j); if i<=j then begin swap(x[i],x[j]); swap(y[i],y[j]); inc(i); dec(j); end; until i>j; if i<r then sortY(i,r); if l<j then sortY(l,j); end; var gt:longint; function find(l,r:longint):longint; inline; begin if c[l]=gt then exit(l); if c[r]=gt then exit(r); mid:=(l+r)>>1; if c[mid]=gt then exit(mid); if gt<c[mid] then exit(find(l,mid-1)) else exit(find(mid+1,r)); end; procedure add(u:longint; var a:list); inline; var p:list; begin new(p); p^.u:=u; p^.next:=a; a:=p; end; procedure solve; var j,i,sl,firsti,firstj,yi,yj,lasti,lastj,cij:longint; l,ss:int64; pi,pj:list; ok:boolean; begin //Khoi tao mang gia tri X sortC(1,n); sl:=1; for i:=2 to n do if c[i]>c[sl] then begin inc(sl); c[sl]:=c[i]; end; //Khoi tao danh sach cac diem co hoanh do X[i] sortY(1,n); for i:=1 to n do begin gt:=x[i]; ind[i]:=find(1,sl); end; for i:=1 to n do add(y[i],ds[ind[i]]); //Dem cac hinh chu nhat thoa man count:=0; smin:=oo; smax:=-1; cmin:=0; cmax:=0; for i:=1 to sl-1 do for j:=i+1 to sl do begin pi:=ds[i]; pj:=ds[j]; l:=c[j]-c[i]; firsti:=pi^.u; pi:=pi^.next; firstj:=pj^.u; pj:=pj^.next; while firsti<>firstj do begin if (pi=nil) or (pj=nil) then break; if firsti<firstj then begin firsti:=pi^.u; pi:=pi^.next; end else begin firstj:=pj^.u; pj:=pj^.next; end; end; if (pi=nil) or (pj=nil) then continue; lasti:=firsti; lastj:=firstj; yi:=pi^.u; yj:=pj^.u; pi:=pi^.next; pj:=pj^.next; cij:=1; ok:=true; while ok do begin if (yi<yj) and (pi<>nil) then begin yi:=pi^.u; pi:=pi^.next; end else if (yi>yj) and (pj<>nil) then begin yj:=pj^.u; pj:=pj^.next; end else ok:=false; if yi=yj then begin ok:=true; inc(count,cij); ss:=l*(yi-lasti); if ss>0 then if ss<smin then begin smin:=ss; cmin:=1; end else if ss=smin then inc(cmin); lasti:=yi; lastj:=yj; inc(cij); if (pi=nil) and (pj=nil) then ok:=false; if pi<>nil then begin yi:=pi^.u; pi:=pi^.next; end; if pj<>nil then begin yj:=pj^.u; pj:=pj^.next; end; end; end; ss:=l*(lasti-firsti); if ss>smax then begin smax:=ss; cmax:=1; end else if ss=smax then inc(cmax); end; end; procedure ans; inline; begin writeln(f2,count); if count=0 then exit; writeln(f2,smax,' ',cmax); writeln(f2,smin,' ',cmin); end; begin openF; inp; solve; ans; closeF; end.
Bình luận