Общий форумthere must be some tricky in P1103 (pensils and cirles) or some wrong things in the test program !!!! 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 :( > > 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 |