Editorial for Xây dựng lâu đài
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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.
Comments