NOT A BLOG | sqybi

TOI 1149 — 城堡围墙

Posted on 七月 13th, 2008.

这里好久没更新了,因为没做什么太好的题.最近做题太少,这几天要开始努力做题了.

可以发现把城堡边界的凸包平移之后,多出来的拐角部分都是圆弧,而这些圆弧恰好可以组成一个圆.所以这道题的答案是凸包的周长+2*pi*l.
第一次写凸包,发现没有想象的那么恶心,反而是异常好写.
代码写得不好看,大牛忽略即可.

{
TOI 1149; 城堡围墙
- sqybi’s code
- 凸包
}
//for my winsty
program toi1149_sqybi;
  const
    fin = ‘wall.in’;
    fout = ‘wall.out’;
    nn = 1000;
    esp = 1e-6;

  type
    rec = record
      x, y: double;
    end;

  var
    n, i, sl1, sl2: longint;
    l, res: double;
    stack1, stack2: array[1..nn]of longint;
    a: array[1..nn]of rec;

  function comp(a, b: rec): boolean;
    begin
      comp := (a.y < b.y) or ((a.y = b.y) and (a.x < b.x));
    end;

  procedure qsort(l, r: longint);
    var
      i, j: longint;
      d, t: rec;
    begin
      if l >= r then exit;
      i := l;
      j := r;
      d := a[(l+r) div 2];
      repeat
        while comp(a[i], d) do inc(i);
        while comp(d, a[j]) do dec(j);
        if i <= j then begin
          t := a[i];
          a[i] := a[j];
          a[j] := t;
          inc(i);
          dec(j);
        end;
      until i > j;
      qsort(l, j);
      qsort(i, r);
    end;

  function crossMult(x1, y1, x2, y2: double): double;
    begin
      crossMult := x1 * y2 - x2 * y1;
    end;

  function check(p, q, r: longint): boolean;
    begin
      check := crossMult(a[q].x-a[p].x, a[q].y-a[p].y, a[r].x-a[q].x, a[r].y-a[q].y) > -esp;
    end;

  function len(i, j: longint): double;
    begin
      len := sqrt(sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y));
    end;

  begin
    assign(input, fin);
    assign(output, fout);
    reset(input);
    rewrite(output);

    readln(n, l);
    for i:=1 to n do readln(a[i].x, a[i].y);
    qsort(1, n);

    res := 0;

    sl1 := 2;
    stack1[1] := 1;
    stack1[2] := 2;
    for i:=3 to n do begin
      while (sl1 > 1) and (not check(stack1[sl1-1], stack1[sl1], i)) do dec(sl1);
      inc(sl1);
      stack1[sl1] := i;
    end;
    for i:=1 to sl1-1 do
      res := res + len(stack1[i], stack1[i+1]);

    sl2 := 2;
    stack2[1] := n;
    stack2[2] := n - 1;
    for i:=n-2 downto 1 do begin
      while (sl2 > 1) and (not check(stack2[sl2-1], stack2[sl2], i)) do dec(sl2);
      inc(sl2);
      stack2[sl2] := i;
    end;
    for i:=1 to sl2-1 do
      res := res + len(stack2[i], stack2[i+1]);

    res := res + 2 * pi * l;
    writeln(res:0:0);

    close(input);
    close(output);
  end.

阅读(52 次)

Make a Comment

Make A Comment: ( 2 so far )

2 Responses to “TOI 1149 — 城堡围墙”

Comments RSS Feed

Where's The Comment Form?