明天就是省选了,今天来报名的人居然只有十几个,更让他们吃惊的是我们学校只去了两个人.

我已经是高二了,这或者是中学OI学习真正的结束又或者是一个全新的开始和全新的挑战.从初中到现在已经接触OI几年了,不管结果如何OI的学习肯定还是会继续,只是说可能学习的重心会怎样变的问题,因为毕竟还有高考.这么多次考试都过去了,关键就看明天这一战,嗯,加油!   

var crest,c,cbak:array[1..32,1..32]of longint;
    a:array[1..32,0..32]of longint;
    ans,l1,l2,l3,cut:array[1..1000]of longint;
    p,q:array[1..32]of longint;
    flow,min,p1,p2,m,n,dep,cn,maxf,sum:longint;   procedure init;
var i,j:longint;
begin
 read(n,m);
 for i:=1 to m do
  begin
   read(l1[i],l2[i],l3[i]);
   inc(c[l1[i],l2[i]],l3[i]);
  end;
 for i:=1 to n do
  for j:=1 to n do
   if c[i,j]>0 then begin
                     inc(a[i,0]);
                     a[i,a[i,0]]:=j;
                     inc(a[j,0]);
                     a[j,a[j,0]]:=i;
                    end;
 cbak:=c;
end;   function find:boolean;
var j:longint;
begin
 fillchar(p,sizeof(p),255);
 p1:=1;p2:=1;
 q[1]:=1; p[1]:=0;
 repeat
  for j:=1 to a[q[p1],0] do
   if (p[a[q[p1],j]]<0)and(c[q[p1],a[q[p1],j]]>0)
     then begin
            inc(p2);
            q[p2]:=a[q[p1],j];
            p[q[p2]]:=q[p1];
            if q[p2]=n then exit(true);
          end;
  inc(p1);
 until p1>p2;
 exit(false);
end;   function maxflow:longint;
var s,i:longint;
begin
 s:=0;
 while true do
  if find then begin
                min:=999999999;i:=n;
                while p[i]<>0 do
                 begin
                  if min>c[p[i],i] then min:=c[p[i],i];
                  i:=p[i];
                 end;
                s:=s+min;
                i:=n;
                while p[i]<>0 do
                 begin
                  dec(c[p[i],i],min);
                  inc(c[i,p[i]],min);
                  i:=p[i];
                 end;
               end
         else break;
 exit(s);
end;   procedure mincut;
var i:longint;
begin
 sum:=0;
 crest:=c;
 for i:=1 to m do
  if crest[l1[i],l2[i]]=0 then
  begin
   c:=cbak;
   dec(c[l1[i],l2[i]],l3[i]);
   if flow-maxflow=l3[i] then begin
                                inc(cn);
                                cut[cn]:=i;
                                inc(sum,l3[i]);
                              end;
  end;
end;   procedure out;
var i:longint;
begin
 writeln(flow,' ',dep);
 for i:=1 to dep do
  writeln(ans[i]);
 halt;
end;   procedure dfs(i,last,s:longint);
var j:longint;
begin
 if i>dep then begin
                if s=flow then out;
                exit;
               end;
 for j:=last+1 to cn do
  begin
   ans[i]:=j;
   dfs(i+1,j,s+l3[j]);
  end;
end;   begin
 init;
 flow:=maxflow;
 mincut;
 if sum=flow then begin
                    ans:=cut;
                    dep:=cn;
                    out;
                  end;
 for dep:=1 to cn do
  dfs(1,0,0);
end.

以最小的点开始,从小到大搜存在一个数组里,最后倒起输出来即可

var
  n,i,j,s,t,m:word;
  con:array[1..500,1..500]of word;
  d:array[1..500]of word;
  cir:boolean;
  path:array[1..1025]of word;
procedure search (s:word);
var
  i:word;
begin
  for i:=1 to m do
    if con[s,i]>0 then
    begin
      dec(con[s,i]);
      dec(con[i,s]);
      search(i);
    end;
  inc(j);
  path[j]:=s;
end;
begin
  readln(n);
  for i:=1 to n do
  begin
    readln(s,t);
    inc(con[s,t]);
    inc(con[t,s]);
    inc(d[s]);
    inc(d[t]);
    if s>m then
      m:=s;
    if t>m then
      m:=t;
  end;
  cir:=true;
  for i:=1 to m do
    if odd(d[i]) then
    begin
      s:=i;
      cir:=false;
      break;
    end;
  j:=0;
  if cir then
    search(1)
  else
    search(s);
  for i:=n+1 downto 1 do
    writeln(path[i]);
end.

对于0≤r≤n,有

C(n,r)=C(n,n-r)

C(n,r)=C(n-1,r)+C(n-1,r-1)

C(n,0)+ C(n+1,1)+ C(n+2,2)+ …+ C(n+r,r)= C(n+r+1,r)

C(n,l)*C(l,r)=C(n,r)*C(n-r,l-r)

C(n,0)+ C(n,1)+…+ C(n,n-1)+ C(n,n)=2n

C(n,0)-C(n,1)+C(n,2)-…±C(n,n)=0

C(m+n,r)=C(m,0)*C(n,r)+C(m,1)*C(n,r-1) +…+C(m,r)*C(n,0)

C(m+n,m)=C(m,0)*C(n,0)+C(m,1)*C(n,1)+…+C(m,m)*C(n,m)

∑j≥0 C(k,j)* C(l,j)* C(n+k+l-j,k+1)= C(n+k,k) C(n+l,l)

给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值
     把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出A^k即可

type
  ss=record
    left,right:longint;
  end;
var
  a:array[1..100]of ss;
  f:array[1..100,0..100]of longint;
  d,b,v,g:array[1..100]of longint;
  i,j,k,l,n,m,o,ans:longint;
  h:array[1..100]of boolean;
function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;
procedure bfs;
var
  now,l,r,k:longint;
begin
  b[1]:=i;l:=0;r:=1;
  d[1]:=i;k:=1;
  repeat
    inc(l);
    now:=b[l];
    if a[now].left<>0 then
    begin
      inc(k);
      d[k]:=a[now].left;
      inc(r);b[r]:=a[now].left;
    end;
    if a[now].right<>0 then
    begin
      inc(k);
      d[k]:=a[now].right;
      inc(r);b[r]:=a[now].right;
    end;
  until l=r;
end;
begin
  readln(n,m);
  if m=1 then
  begin
    writeln(1);halt;
  end;
  for i:=1 to n-1 do
  begin
    readln(j,k);
    if v[j]=0 then
      a[j].left:=k
    else a[v[j]].right:=k;
    v[j]:=k;
    h[k]:=true;
  end;
  for i:=1 to n do
  if not h[i] then
    break;
  bfs;
  for i:=1 to n do
  for j:=0 to m do
    f[i,j]:=maxint;
  for l:=n downto 1 do
  begin
    i:=d[l];
    g[i]:=1;
    if a[i].right<>0 then
    begin
      inc(g[i],g[a[i].right]);
      f[i,0]:=f[a[i].right,0]+1;
    end
    else f[i,0]:=1;
    if a[i].left<>0 then inc(g[i],g[a[i].left]);
    for j:=1 to m do
    if j>g[i] then break
    else
    begin
      if a[i].right<>0 then
      begin
        f[i,j]:=min(f[i,j],f[a[i].right,j]+1);
        if a[i].left=0 then
        begin
          f[i,j]:=min(f[i,j],f[a[i].right,j-1]);
          continue;
        end
        else f[i,j]:=min(f[i,j],f[a[i].right,j-1]+1)
      end
      else
      begin
        if a[i].left<>0 then
          f[i,j]:=f[a[i].left,j-1]
        else f[i,j]:=0;
        continue;
      end;
      for k:=1 to j-1 do
      if k>g[a[i].left] then break
      else f[i,j]:=min(f[i,j],f[a[i].left,k]+f[a[i].right,j-k-1]);
    end;
  end;
  ans:=maxlongint;
  for i:=1 to n do
  if d[1]<>i then
    if a[i].left<>0 then
      ans:=min(ans,f[a[i].left,m-1]+1)
    else
  else ans:=min(ans,f[a[i].left,m-1]);
  writeln(ans);
end.

因为gcd的复杂度是logn(底数不为2,跟Fibonacci数列通项有关,约等于1.618)

var
  m,a:array[1..100000]of longint;
  i,n,d,ans,x,y,o:longint;
function gcd(a,b:longint;var x,y:longint):longint;
var
  t:longint;
begin
  if b=0 then
  begin
    x:=1;y:=0;
    exit(a);
  end;
  gcd:=gcd(b,a mod b,x,y);
  t:=x;
  x:=y;
  y:=t-a div b*y;
end;
begin
  readln(n);
  o:=1;
  for i:=1 to n do
  begin
    readln(m[i],a[i]);
    o:=o*m[i];
  end;
  for i:=1 to n do
  begin
    d:=gcd(o div m[i],m[i],x,y);
    m[i]:=m[i] div d;    {不互质时改值}
    o:=o div d;
    a[i]:=a[i] mod m[i];
    d:=gcd(o div m[i],m[i],x,y);
    x:=(x mod m[i]+m[i])mod m[i];{保证x为正数}
    inc(ans,o div m[i]*x*a[i]);
  end;
  writeln(ans mod o);
end.

实践证明比bellman-ford判负环快

type
  link=^rec;
  rec=record
    e,i:longint;
    point:link;
  end;
function spfa:boolean;{n个点 m条边}
var
  now,l,r,i:longint;
  b,f:array[1..1000]of longint;
  h:array[1..1000]of boolean;
  p:link;
begin
  for i:=1 to n do f[i]:=maxlongint;
  f[1]:=0;
  fillchar(d,sizeof(d),0);
  fillchar(h,sizeof(h),0);
  l:=0;r:=1;
  h[1]:=true;b[1]:=i;
  repeat
    inc(l);if l>1000 then l:=1;{循环队列}
    now:=b[l];
    p:=v[now];
    while p<>nil do
    begin
      if f[now]+p^.e<f[p^.i] then
      begin
        inc(d[now]);if d[now]>m then exit(true);{某个点用的次数超过边数则肯定存在负环}
        f[p^.i]:=f[now]+p^.e;
        if not h[p^.i] then
        begin
          inc(r);if r>1000 then r:=1;
          b[r]:=p^.i;
        end;
      end;
      p:=p^.point;
    end;
    h[now]:=false;
  until l=r;
  exit(false);
end;

1.把个数表示成若干个2^k次方形式,再用01背包做  O(nvlogv)

var
    v,i,j,k,l,n,max,o,d:longint;
    f,a,w:array[0..10000]of longint;
begin
    readln(n,v);
    for i:=1 to n do
    begin
        readln(j,k,d);
        o:=1;
        while d-o shl 1+1>=0 do
        begin
            inc(l);a[l]:=o*j;w[l]:=o*k;
            o:=o shl 1;
        end;
        o:=d-o+1;
        inc(l);a[l]:=o*j;w[l]:=o*k;
    end;
    for i:=1 to l do
      for j:=v downto a[i] do
        if f[j-a[i]]+w[i]>f[j] then
           f[j]:=f[j-a[i]]+w[i];
    for i:=1 to v do
      if f[i]>max then max:=f[i];
    writeln(max);
end.

2.队列优化 O(nv)

var
  l,r,f,a,w,d:array[0..10000]of longint;
  b:array[0..1000,1..10000]of longint;
  v,i,j,k,n,t:longint;
function max(a,b:longint):longint;
begin
  if a<b then exit(b) else exit(a);
end;
begin
  readln(n,v);
  for i:=1 to n do readln(a[i],w[i],d[i]);
  for i:=1 to n do
  begin
    fillchar(b,sizeof(b),0);
    if a[i]>v then continue;
    for j:=v downto v-a[i]+1 do
    begin
      t:=j mod a[i];
      r[t]:=0;
      for k:=1 to d[i] do
      if j-k*a[i]<0  then break
      else
      begin
        while (r[t]>0)and(f[j-k*a[i]]+k*w[i]>f[b[t,r[t]]]+w[i]*(j-b[t,r[t]])div a[i]) do
          dec(r[t]);
        inc(r[t]);
        b[t,r[t]]:=j-k*a[i];
      end;
      if r[t]>0 then
      begin
        f[j]:=max(f[j],f[b[t,1]]+w[i]*(j-b[t,1])div a[i]);
        if b[t,1]=j-a[i] then l[t]:=2
        else l[t]:=1;
      end
      else l[t]:=1;
    end;
    for j:=v-a[i] downto a[i] do
    begin
      t:=j mod a[i];
      while (r[t]>=l[t])and(j-d[i]*a[i]>=0)and
      (f[j-d[i]*a[i]]+d[i]*w[i]>f[b[t,r[t]]]+w[i]*(j-b[t,r[t]])div a[i]) do
        dec(r[t]);
      if j-d[i]*a[i]>=0 then
      begin
        inc(r[t]);
        b[t,r[t]]:=j-d[i]*a[i];
      end;
      if r[t]>=l[t] then
        f[j]:=max(f[j],f[b[t,l[t]]]+w[i]*(j-b[t,l[t]])div a[i]);
      if b[t,l[t]]=j-a[i] then inc(l[t]);
    end;
  end;
  for i:=1 to v do f[i]:=max(f[i-1],f[i]);
  writeln(f[v]);
end.

n个作业要在由两台机器M1和M2组成的流水线上完成加工. 每个作业i必须先在M1上然后在M2上加工, 时间分别为ai和bi

确定这n个作业的加工顺序, 使得从第一个任务开始在M1上加工到最后一个任务在M2上加工完成的总时间尽量小

Johnson算法.
设N1为a<b的作业集合, N2为a>=b的作业集合, 将N1的作业按a非减序排序, N2中的作业按照b非增序排序, 则N1作业接N2作业构成最优顺序.(证明略)

type
  heap=^rec;
  rec=record
    left,right:heap;
    x,d:longint;
  end;
var
  p,h:heap;
  i,k,n:longint;
function merge(var a,b:heap):heap;
var
  c:heap;
begin
  if a=nil then exit(b);
  if b=nil then exit(a);
  if a^.x>b^.x then
  begin
    c:=a;a:=b;b:=c;
  end;
  a^.right:=merge(a^.right,b);
  if (a^.left=nil)or(a^.left^.d<=a^.right^.d) then
  begin
    c:=a^.left;a^.left:=a^.right;a^.right:=c;
  end;
  if a^.right=nil then a^.d:=0
  else a^.d:=a^.right^.d+1;
  exit(a);
end;
begin
  readln(n);
  for i:=1 to n do
  begin
    read(k);
    new(p);
    p^.x:=k;p^.left:=nil;p^.right:=nil;p^.d:=0;
    h:=merge(p,h);
  end;
  for i:=1 to n do
  begin
    writeln(h^.x);
    h:=merge(h^.left,h^.right);
  end;
end.

还是觉得递归+函数返回的形式比较科学

type
  tree=^rec;
  rec=record
    left,right:tree;
    ld,rd,x:longint;
    e:double;
  end;
function left(var p:tree):tree;{左旋}
var
  t:tree;
begin
  t:=p^.left;p^.left:=t^.right;t^.right:=p;
  dec(p^.ld,t^.ld+1);
  inc(t^.rd,p^.rd+1);
  exit(t);
end;

function right(var p:tree):tree;{右旋}
var
  t:tree;
begin
  t:=p^.right;p^.right:=t^.left;t^.left:=p;
  dec(p^.rd,t^.rd+1);
  inc(t^.ld,p^.ld+1);
  exit(t);
end;

function insert(x:longint;var p:tree):tree;{插入x元素}
begin
  if p=nil then
  begin
    writeln(o+1);{输出它是第几大}
    new(p);
    p^.left:=nil;p^.right:=nil;
    p^.x:=x;p^.ld:=0;p^.rd:=0;p^.e:=random;
    exit(p);
  end;
  if x<p^.x then
  begin
    inc(o,p^.rd+1);{o记录比x大的有多少}
    p^.left:=insert(x,p^.left);
    inc(p^.ld);
    if p^.left^.e<p^.e then
      p:=left(p);
    exit(p);
  end
  else
  begin
    p^.right:=insert(x,p^.right);
    inc(p^.rd);
    if p^.right^.e<p^.e then
      p:=right(p);
    exit(p);
  end;
end;

function delete(var p:tree):tree;{删除p节点}
begin
  if (p^.left=nil)and(p^.right=nil) then
  begin
    dispose(p);
    exit(nil);
  end;
  if (p^.left<>nil)and((p^.right=nil)or(p^.left^.e<p^.right^.e)) then
  begin
    p:=left(p);
    p^.right:=delete(p^.right);
    dec(p^.rd);
    exit(p);
  end
  else
  begin
    p:=right(p);
    p^.left:=delete(p^.left);
    dec(p^.ld);
    exit(p);
  end;
end;

function find(x:longint;var p:tree):tree; {查找第x大元素}
begin
  if o+p^.rd+1=x then{o记录该节点的上面有多少比它大,初始值为0}
  begin
    writeln(p^.x);{输出这个数并删除}
    p:=delete(p);{如果需要删除}
    exit(p);
  end;
  if x<o+p^.rd+1 then
  begin
    p^.right:=find(x,p^.right);
    dec(p^.rd);{只是查找就不变}
    exit(p);
  end
  else
  begin
    inc(o,p^.rd+1);
    p^.left:=find(x,p^.left);
    dec(p^.ld);
    exit(p);
  end;
end;

type
  link=^rec;
  rec=record
    i,e:longint;
    point:link;
  end;
var
  v:array[1..1000]of link;
  p:link;
  f:array[1..1000]of boolean;
  a,g:array[1..1000,1..1000]of longint;
  t:array[1..1000,1..1000]of boolean;
  d,b:array[1..1000]of longint;
  ans,i,j,k,l,n,m,o:longint;
procedure dfs(i,j,o:longint);
var
  p:link;
begin
  a[i,j]:=o;
  f[j]:=true;
  p:=v[j];
  while p<>nil do
  begin
    if not f[p^.i] then
      if p^.e>o then
        dfs(i,p^.i,p^.e)
      else dfs(i,p^.i,o);
    p:=p^.point;
  end;
end;
begin
  readln(n,m);
  for i:=1 to n do
  for j:=1 to n do
    g[i,j]:=maxlongint;
  for i:=1 to n do d[i]:=maxlongint;
  for i:=1 to m do
  begin
    readln(j,k,l);
    g[j,k]:=l;g[k,j]:=l;
    if k=1 then
    begin
      b[j]:=1;d[j]:=l;
    end;
    if j=1 then
    begin
      b[k]:=1;d[k]:=l;
    end;
  end;
  f[1]:=true;
  for i:=1 to n-1 do
  begin
    k:=0;o:=maxlongint;
    for j:=2 to n do
    if (not f[j])and(d[j]<o) then
    begin
      o:=d[j];k:=j;
    end;
    f[k]:=true;inc(ans,o);
    for j:=2 to n do
    if (not f[j])and(g[k,j]<d[j]) then
    begin
      d[j]:=g[k,j];b[j]:=k;
    end;
  end;
  for i:=2 to n do
  begin
    t[i,b[i]]:=true;t[b[i],i]:=true;
    new(p);
    p^.i:=b[i];p^.e:=g[i,b[i]];
    p^.point:=v[i];v[i]:=p;
    new(p);
    p^.i:=i;p^.e:=g[i,b[i]];
    p^.point:=v[b[i]];v[b[i]]:=p;
  end;
  for i:=1 to n do
  begin
    fillchar(f,sizeof(f),0);
    dfs(i,i,0);
  end;
  o:=maxlongint;
  for i:=1 to n-1 do
  for j:=i+1 to n do
  if (not t[i,j])and(g[i,j]-a[i,j]<o) then
    o:=g[i,j]-a[i,j];
  writeln(ans+o);
end.

type
  ss=array[0..100]of byte;
function bigger(a,b:ss):boolean;
var
  i:longint;
begin
  if a[0]<>b[0] then
    if a[0]<b[0] then
      exit(false)
    else exit(true);
  for i:=a[0] downto 1 do
  if a[i]<>b[i] then
    if a[i]<b[i] then
      exit(false)
    else exit(true);
  exit(true);
end;

function jia(a,b:ss):ss;
var
  i,o,k,l:longint;
begin
  l:=max(a[0],b[0])+1;
  k:=0;
  for i:=1 to l do
  begin
    o:=a[i]+b[i]+k;
    a[i]:=o mod 10;
    k:=o div 10;
  end;
  while (a[a[0]]=0)and(a[0]>1) do dec(a[0]);
  exit(a);
end;

function jian(a,b:ss):ss;
var
  i,o,k:longint;
begin
  k:=0;
  for i:=1 to a[0] do
  begin
    o:=a[i]+10-b[i]-k;
    a[i]:=o mod 10;
    k:=1-o div 10;
  end;
  while (a[a[0]]=0)and(a[0]>1) do dec(a[0]);
  exit(a);
end;

function cheng(a:ss;x:longint):ss;
var
  i,o,k:longint;
begin
  inc(a[0],trunc(ln(x)/ln(10))+1);
  k:=0;
  for i:=1 to a[0] do
  begin
    o:=a[i]*x+k;
    a[i]:=o mod 10;
    k:=o div 10;
  end;
  while (a[a[0]]=0)and(a[0]>1) do dec(a[0]);
  exit(a);
end;

function cheng2(a,b:ss):ss;
var
  i,j,o,k:longint;
  c:ss;
begin
  c[0]:=a[0]+b[0]+1;
  for i:=1 to a[0]+1 do
  begin
    k:=0;
    for j:=1 to b[0]+1 do
    begin
      o:=a[i]*b[j]+c[i+j-1]+k;
      c[i+j-1]:=o mod 10;
      k:=o div 10;
    end;
  end;
  while (c[c[0]]=0)and(c[0]>1) do dec(c[0]);
  exit(c);
end;

function chu(a:ss;x:longint;var rest:longint):ss;
var
  i,o:longint;
begin
  rest:=0;
  for i:=a[0] downto 1 do
  begin
    o:=rest*10+a[i];
    rest:=o mod x;
    a[i]:=o div x;
  end;
  while (a[a[0]]=0)and(a[0]>1) do dec(a[0]);
  exit(a); 
end;

function chu2(a,b:ss;var ans,rest:ss):ss;
var
  l,i:longint;
begin
  fillchar(rest,sizeof(rest),0);
  rest[0]:=1;
  for i:=a[0] downto 1 do
  begin
    rest:=cheng(rest,10);
    rest[1]:=a[i];l:=0;
    while bigger(rest,b) do
    begin
      rest:=jian(rest,b);
      inc(l);
    end;
    a[i]:=l;
  end;
  while (a[a[0]]=0)and(a[0]>1) do dec(a[0]);
  exit(a);
end;

var
  a,w:array[1..60,0..10]of longint;
  f:array[0..200000]of longint;
  i,j,k,l,n,o,v:longint;
function max(a,b:longint):longint;
begin
  if a>b then exit(a) else exit(b);
end;
begin
  readln(v,n);
  for i:=1 to n do
  begin
    readln(j,k,l);
    if l=0 then l:=i;
    inc(a[l,0]);
    a[l,a[l,0]]:=j;w[l,a[l,0]]:=j*k;
  end;
  for i:=1 to n do
  if a[i,0]>0 then
  begin
    fillchar(f,sizeof(f),0);
    for j:=2 to a[i,0] do
    for k:=v-a[i,1] downto a[i,j] do
    if (f[k-a[i,j]]>0)or(k=a[i,j]) then
      f[k]:=max(f[k],f[k-a[i,j]]+w[i,j]);
    l:=0;k:=a[i,1];o:=w[i,1];
    for j:=0 to v-k do
    if (f[j]<>0)or(j=0) then
    begin
      inc(l);
      a[i,l]:=k+j;w[i,l]:=f[j]+o;
    end;
    a[i,0]:=l;
  end;
  fillchar(f,sizeof(f),0);
  for i:=1 to n do
  for k:=v downto 0 do
  for j:=1 to a[i,0] do
  if k>=a[i,j] then
    f[k]:=max(f[k],f[k-a[i,j]]+w[i,j]);
  for i:=1 to v do f[i]:=max(f[i-1],f[i]);
  writeln(f[v]);
end.

for 所有的组k

for v=V..0

for 所有的i属于组k

f[v]=max{f[v],f[v-c[i]]+w[i]}

扩展的辗转相除：http://acm.pku.edu.cn/JudgeOnline/problem?id=2115 较科学

最优匹配KM算法：http://acm.pku.edu.cn/JudgeOnline/problem?id=2195 不科学

强连通分量：http://acm.pku.edu.cn/JudgeOnline/problem?id=2553 科学

求割点个数：http://acm.pku.edu.cn/JudgeOnline/problem?id=1144 不科学

最小割：http://acm.pku.edu.cn/JudgeOnline/problem?id=2125 很科学

计算几何：http://acm.pku.edu.cn/JudgeOnline/problem?id=3023 不科学
图片地址应该是http://acm.pku.edu.cn/JudgeOnline/images/3023_1.jpg

凸包：http://acm.pku.edu.cn/JudgeOnline/problem?id=1113 较科学

半平面相交：http://acm.pku.edu.cn/JudgeOnline/problem?id=3384 很科学

欧拉回路+trie：http://acm.pku.edu.cn/JudgeOnline/problem?id=2513 不科学

Tarjan算法：http://acm.pku.edu.cn/JudgeOnline/problem?id=1986 不科学
输入格式另见http://acm.pku.edu.cn/JudgeOnline/problem?id=1984

100 熟悉环境题
101 欧拉回路
102 数学
103 最短路
104 DP
105 数学
106 数学
107 数学
108 数学
109 构造
110 计算几何
111 数学
112 简单题
113 枚举
114 数学
115 简单题
116 DP
117 数学
118 数学
119 数学
120 计算几何
121 欧拉路
122 Hamilton回路
123 简单题
124 计算几何
125 搜索
126 数学
127 统计
128 构造
129 计算几何
130 Catalan数
131 DP
132 DP
133 简单题
134 树规
135 数学
136 数学
137 构造
138 贪心
139 数学
140 数学
141 数学
142 数学
143 树规
144 概率
145 二分答案
146 数学
147 枚举
148 贪心
149 树规

type
  ss=record
    x,y,c:double;
  end;
var
  a,b:array[1..100000]of ss;
  i,j,n:longint;
  d:ss;
  o:double;
procedure qsort(l,r:longint);
var
  i,j:longint;
  mid,midx:double;
  k:ss;
begin
  i:=l;j:=r;mid:=a[(l+r)shr 1].c;midx:=a[(l+r)shr 1].x;
  repeat
    while (a[i].c<mid)or((a[i].c=mid)and(abs(a[i].x-d.x)<abs(midx-d.x))) do inc(i);
    while (a[j].c>mid)or((a[j].c=mid)and(abs(a[j].x-d.x)>abs(midx-d.x))) do dec(j);
    if i<=j then
    begin
      k:=a[i];a[i]:=a[j];a[j]:=k;
      inc(i);dec(j);
    end;
  until i>j;
  if j>l then qsort(l,j);
  if i<r then qsort(i,r);
end;
begin
  readln(n);
  d.y:=maxlongint;
  for i:=1 to n do
  begin
    readln(a[i].x,a[i].y);
    if (a[i].y<d.y)or((a[i].y=d.y)and(a[i].x<d.x)) then
      d:=a[i];
  end;
  for i:=1 to n do
    if (d.x<>a[i].x)or(d.y<>a[i].y) then
      a[i].c:=(d.x-a[i].x)/sqrt(sqr(a[i].x-d.x)+sqr(a[i].y-d.y))
    else a[i].c:=-1;
  qsort(1,n);
  b[1]:=a[1];b[2]:=a[2];a[n+1]:=a[1];j:=2;
  for i:=3 to n+1 do
  begin
    while (b[j].x-b[j-1].x)*(a[i].y-b[j-1].y)<(a[i].x-b[j-1].x)*(b[j].y-b[j-1].y) do
      dec(j);
    inc(j);b[j]:=a[i];
  end;
  for i:=1 to j-1 do writeln(b[i].x:0:2,' ',b[i].y:0:2);
end.

{
ID:whqlsc1
LANG:PASCAL
TASK:fence4
}
type
  ss=record
    c,x,y:double;
  end;
var
  a,b:array[1..200]of ss;
  f:array[1..200]of boolean;
  i,j,k,l,n,m,o:longint;
  e:double;
  p,d,c:ss;
function chaji(a,b,c,d:ss):double;
var
  x1,x2,y1,y2:double;
begin
  x1:=b.x-a.x;y1:=b.y-a.y;
  x2:=d.x-c.x;y2:=d.y-c.y;
  exit(x1*y2-x2*y1);
end;
function xiangjiao(a,b,c,d:ss):boolean;
begin
  if (chaji(a,c,a,b)*chaji(a,d,a,b)<0)and(chaji(c,a,c,d)*chaji(c,b,c,d)<0) then
    exit(true)
  else exit(false);
end;
function xiangjiao2(a,b,c,d:ss;var p:ss):boolean;
var
  s1,s2,s3:double;
begin
  s1:=chaji(a,b,a,c);
  s2:=chaji(a,b,a,d);
  s3:=chaji(a,c,a,d);
  if (s1*s2>=0)or(s1*s3>=0) then exit(false);
  p.x:=(s2*c.x-s1*d.x)/(s2-s1);
  p.y:=(s2*c.y-s1*d.y)/(s2-s1);
  exit(true);
end;
begin
  assign(input,'fence4.in');
  assign(output,'fence4.out');
  reset(input);
  rewrite(output);
  readln(n);
  readln(d.x,d.y);
  for i:=1 to n do
  begin
    readln(a[i].x,a[i].y);
    if a[i].y>=d.y then
      k:=1
    else k:=-1;
    if (a[i].x<>d.x)or(a[i].y<>d.y) then
      a[i].c:=((a[i].x-d.x)/sqrt(sqr(a[i].x-d.x)+sqr(a[i].y-d.y))+1)*k
    else a[i].c:=2;
  end;
  a[n+1]:=a[1];
  for i:=1 to n-2 do
  for j:=i+2 to n do
  if xiangjiao(a[i],a[i+1],a[j],a[j+1]) then
  begin
    writeln('NOFENCE');
    close(output);halt;
  end;
  b:=a;
  for i:=1 to n do
  for j:=1 to n-1 do
  if b[j].c<b[j+1].c then
  begin
    c:=b[j];b[j]:=b[j+1];b[j+1]:=c;
  end;
  b[n+1]:=b[1];o:=0;
  for i:=1 to n do
  if chaji(d,b[i],d,b[i+1])>0 then
  begin
    c.x:=(b[i].x+b[i+1].x)/2;
    c.y:=(b[i].y+b[i+1].y)/2;
    e:=0;k:=0;
    for j:=1 to n do
    if xiangjiao2(d,c,a[j],a[j+1],p) then
      if (k=0)or(abs(p.x-d.x)+abs(p.y-d.y)<e) then
      begin
        k:=j;e:=abs(p.x-d.x)+abs(p.y-d.y);
      end;
    if k<>0 then
    begin
      if not f[k] then inc(o);
      f[k]:=true;
    end;
  end;
  writeln(o);
  for i:=1 to n-2 do
  if f[i] then
    writeln(a[i].x:0:0,' ',a[i].y:0:0,' ',a[i+1].x:0:0,' ',a[i+1].y:0:0);
  if f[n] then
    writeln(a[1].x:0:0,' ',a[1].y:0:0,' ',a[n].x:0:0,' ',a[n].y:0:0);
  if f[n-1] then
    writeln(a[n-1].x:0:0,' ',a[n-1].y:0:0,' ',a[n].x:0:0,' ',a[n].y:0:0);
  close(output);
end.