ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Common Board

there must be some tricky in P1103 (pensils and cirles) or some wrong things in the test program !!!!
Posted by Dinh Quang Hiep (mg9h@yahoo.com) 15 Jun 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!
Posted by snake 16 Jun 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 :(
Posted by Dinh Quang Hiep (mg9h@yahoo.com) 16 Jun 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