NOT A BLOG | sqybi

TOI 1125 — 搬石头

Posted on 七月 14th, 2008.

给定一个多边形,求重心.
其实只需要随便找一个点,然后围绕它分割成若干个三角形.三角形的重心可以用三顶点坐标的平均数表示,然后重心的权值就是三角形的有向面积.最后对重心坐标加权求平均数就行.不用管多边形是顺时针还是逆时针给出,也不用管是凸还是凹.

一定要记得,输出的时候加上一个eps!不然会有-0.00的诡异错误!
我就是不听RoBa话输出时没加eps导致三个点WA掉…

{
TOI 1125; 搬石头
- sqybi’s code
- 求多边形重心
}
//for my winsty
program toi1125_sqybi;
  const
    fin = ’stone.in’;
    fout = ’stone.out’;
    nn = 1000000;
    eps = 1e-6;

  var
    n, i: longint;
    a, b: array[1..nn]of record
      x, y: double;
    end;
    c: array[1..nn]of double;
    totx, toty, totn: double;

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

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

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

    for i:=2 to n-1 do begin
      b[i-1].x := (a[1].x + a[i].x + a[i+1].x) / 3;
      b[i-1].y := (a[1].y + a[i].y + a[i+1].y) / 3;
      c[i-1] := crossMult(a[i].x-a[1].x, a[i].y-a[1].y, a[i+1].x-a[1].x, a[i+1].y-a[1].y);
      c[i-1] := c[i-1] / 2;
    end;

    totx := 0;
    toty := 0;
    totn := 0;
    for i:=1 to n-2 do begin
      totx := totx + b[i].x * c[i];
      toty := toty + b[i].y * c[i];
      totn := totn + c[i];
    end;

    writeln(totx/totn+eps:0:2, ‘ ‘, toty/totn+eps:0:2);

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

阅读(52 次)

Make a Comment

Make A Comment: ( 2 so far )

2 Responses to “TOI 1125 — 搬石头”

Comments RSS Feed

Where's The Comment Form?