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.

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

Please read the guidelines before commenting.


There are no comments at the moment.