ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Общий форум

there must be some tricky in P1103 (pensils and cirles) or some wrong things in the test program !!!!
Послано Dinh Quang Hiep (mg9h@yahoo.com) 15 июн 2001 22:13
please tell me some wrong thing, i've added a test function
to my source code, and it'll "repeat until false" if my
output is wrong, but i still get WA ? WHY ???????

QH@
I agree with you!
Послано snake 16 июн 2001 18:33

const
  maxn = 6000;

type
  Tpoint = record
    x, y: comp;
    v: double;
  end;

var
  n, kind: integer;
  p: array[1 .. maxn] of Tpoint;

procedure init;
var
  i: integer;
begin
  readln(n);
  for i := 1 to n do readln(p[i].x, p[i].y);
end;

function vector(p, A, B: Tpoint): integer;
var
  v: comp;
begin
  v := (A.x - p.x) * (B.y - p.y) - (A.y - p.y) * (B.x -
p.x);
  if v > 0 then result := 1 else if v < 0 then result := -
1 else result := 0;
end;

function scalar(p, A, B: Tpoint): comp;
begin
  result := (A.x - p.x) * (B.x - p.x) + (A.y - p.y) * (B.y -
 p.y);
end;

function len(A, B: Tpoint): double;
begin
  result := sqrt(sqr(A.x - B.x) + sqr(A.y - B.y));
end;

function more(A, B: Tpoint): boolean;
begin
  if kind = 0 then result := vector(p[1], A, B) >= 0 else
result := A.v >= B.v;
end;

procedure qsort(l, u: integer);
var
  i, j: integer;
  q: Tpoint;
begin
  while l < u do begin
    i := random(u - l + 1) + l;
    q := p[i]; p[i] := p[l]; p[l] := q;
    i := l; j := u;
    while i < j do begin
      while (i < j) and more(p[j], q) do j := j - 1;
      p[i] := p[j];
      while (i < j) and more(q, p[i]) do i := i + 1;
      p[j] := p[i];
    end;
    p[i] := q;
    if i - l < u - i then begin
      qsort(l, i - 1); l := i + 1;
    end else begin
      qsort(i + 1, u); u := i - 1;
    end;
  end;
end;

procedure sort;
var
  i, k: integer;
  q: Tpoint;
begin
  k := 1;
  for i := 2 to n do
    if (p[i].x < p[k].x) or (p[i].x = p[k].x) and (p[i].y <
p[k].y) then
      k := i;
  q := p[1]; p[1] := p[k]; p[k] := q;
  kind := 0; qsort(2, n);
  for i := 3 to n do
    p[i].v := scalar(p[i], p[1], p[2]) / len(p[i], p[1]) /
len(p[i], p[2]);
  kind := 1; qsort(3, n);
end;

procedure print;
begin
  writeln(p[1].x : 0 : 0, ' ', p[1].y : 0 : 0);
  writeln(p[2].x : 0 : 0, ' ', p[2].y : 0 : 0);
  writeln(p[(n - 3) shr 1 + 3].x : 0 : 0, ' ', p[(n - 3)
shr 1 + 3].y : 0 : 0);
end;

function check: boolean;
const
  error = 1e-5;

type
  Tline = record
    a, b, c: double;
  end;

  Trealpoint = record
    x, y: double;
  end;

var
  A, B, C: Tpoint;
  O: Trealpoint;
  AB, AC: Tline;
  i, inside, outside, side: integer;
  r: double;

procedure make(A, B: Tpoint; var AB: Tline);
begin
  AB.a := A.x - B.x; AB.b := A.y - B.y;
  AB.c := ((A.x + B.x) * AB.a + (A.y + B.y) * AB.b) / 2;
end;

procedure cross(A, B: Tline; var p: Trealpoint);
begin
  p.y := (A.c * B.a - B.c * A.a) / (A.b * B.a - A.a * B.b);
  p.x := (A.c * B.b - B.c * A.b) / (A.a * B.b - A.b * B.a);
end;

function len(A: Trealpoint; B: Tpoint): double;
begin
  len := sqrt(sqr(A.x - B.x) + sqr(A.y - B.y));
end;

begin
  A := p[1]; B := p[2]; C := p[(n - 3) shr 1 + 3];
  make(A, B, AB); make(A, C, AC); cross(AB, AC, O);
  r := len(O, A);
  inside := 0; outside := 0; side := 0;
  for i := 1 to n do
    if len(O, p[i]) < r - error then inc(inside) else
    if len(O, p[i]) > r + error then inc(outside) else
    inc(side);
  check := (side = 3) and (inside = outside);
end;

procedure run;
begin
  init;
  sort;
  print;
  if not check then while true do ;
end;

begin
  run;
end.
Re: I agree with you! <= don't put your source here, please tell me the tricky :(
Послано Dinh Quang Hiep (mg9h@yahoo.com) 16 июн 2001 22:14
>
> const
>   maxn = 6000;
>
> type
>   Tpoint = record
>     x, y: comp;
>     v: double;
>   end;
>
> var
>   n, kind: integer;
>   p: array[1 .. maxn] of Tpoint;
>
> procedure init;
> var
>   i: integer;
> begin
>   readln(n);
>   for i := 1 to n do readln(p[i].x, p[i].y);
> end;
>
> function vector(p, A, B: Tpoint): integer;
> var
>   v: comp;
> begin
>   v := (A.x - p.x) * (B.y - p.y) - (A.y - p.y) * (B.x -
> p.x);
>   if v > 0 then result := 1 else if v < 0 then result := -
> 1 else result := 0;
> end;
>
> function scalar(p, A, B: Tpoint): comp;
> begin
>   result := (A.x - p.x) * (B.x - p.x) + (A.y - p.y) * (B.y
-
>  p.y);
> end;
>
> function len(A, B: Tpoint): double;
> begin
>   result := sqrt(sqr(A.x - B.x) + sqr(A.y - B.y));
> end;
>
> function more(A, B: Tpoint): boolean;
> begin
>   if kind = 0 then result := vector(p[1], A, B) >= 0 else
> result := A.v >= B.v;
> end;
>
> procedure qsort(l, u: integer);
> var
>   i, j: integer;
>   q: Tpoint;
> begin
>   while l < u do begin
>     i := random(u - l + 1) + l;
>     q := p[i]; p[i] := p[l]; p[l] := q;
>     i := l; j := u;
>     while i < j do begin
>       while (i < j) and more(p[j], q) do j := j - 1;
>       p[i] := p[j];
>       while (i < j) and more(q, p[i]) do i := i + 1;
>       p[j] := p[i];
>     end;
>     p[i] := q;
>     if i - l < u - i then begin
>       qsort(l, i - 1); l := i + 1;
>     end else begin
>       qsort(i + 1, u); u := i - 1;
>     end;
>   end;
> end;
>
> procedure sort;
> var
>   i, k: integer;
>   q: Tpoint;
> begin
>   k := 1;
>   for i := 2 to n do
>     if (p[i].x < p[k].x) or (p[i].x = p[k].x) and (p[i].y
<
> p[k].y) then
>       k := i;
>   q := p[1]; p[1] := p[k]; p[k] := q;
>   kind := 0; qsort(2, n);
>   for i := 3 to n do
>     p[i].v := scalar(p[i], p[1], p[2]) / len(p[i], p[1]) /
> len(p[i], p[2]);
>   kind := 1; qsort(3, n);
> end;
>
> procedure print;
> begin
>   writeln(p[1].x : 0 : 0, ' ', p[1].y : 0 : 0);
>   writeln(p[2].x : 0 : 0, ' ', p[2].y : 0 : 0);
>   writeln(p[(n - 3) shr 1 + 3].x : 0 : 0, ' ', p[(n - 3)
> shr 1 + 3].y : 0 : 0);
> end;
>
> function check: boolean;
> const
>   error = 1e-5;
>
> type
>   Tline = record
>     a, b, c: double;
>   end;
>
>   Trealpoint = record
>     x, y: double;
>   end;
>
> var
>   A, B, C: Tpoint;
>   O: Trealpoint;
>   AB, AC: Tline;
>   i, inside, outside, side: integer;
>   r: double;
>
> procedure make(A, B: Tpoint; var AB: Tline);
> begin
>   AB.a := A.x - B.x; AB.b := A.y - B.y;
>   AB.c := ((A.x + B.x) * AB.a + (A.y + B.y) * AB.b) / 2;
> end;
>
> procedure cross(A, B: Tline; var p: Trealpoint);
> begin
>   p.y := (A.c * B.a - B.c * A.a) / (A.b * B.a - A.a *
B.b);
>   p.x := (A.c * B.b - B.c * A.b) / (A.a * B.b - A.b *
B.a);
> end;
>
> function len(A: Trealpoint; B: Tpoint): double;
> begin
>   len := sqrt(sqr(A.x - B.x) + sqr(A.y - B.y));
> end;
>
> begin
>   A := p[1]; B := p[2]; C := p[(n - 3) shr 1 + 3];
>   make(A, B, AB); make(A, C, AC); cross(AB, AC, O);
>   r := len(O, A);
>   inside := 0; outside := 0; side := 0;
>   for i := 1 to n do
>     if len(O, p[i]) < r - error then inc(inside) else
>     if len(O, p[i]) > r + error then inc(outside) else
>     inc(side);
>   check := (side = 3) and (inside = outside);
> end;
>
> procedure run;
> begin
>   init;
>   sort;
>   print;
>   if n