program inside; var c : char; vidx : integer; i, j : integer; center_x, center_y : integer; vertex_x : array[0..1000] of integer; vertex_y : array[0..1000] of integer; done : boolean; cond : integer; function max(x:integer; y: integer): integer; begin if (x > y) then begin max := x; end else begin max := y; end; end; function min(x:integer; y: integer): integer; begin if (x < y) then begin min := x; end else begin min := y; end; end; procedure swap( i, j : integer) ; var tmp : integer; begin tmp := vertex_x[j]; vertex_x[j] := vertex_x[i]; vertex_x[i] := tmp; tmp := vertex_y[j]; vertex_y[j] := vertex_y[i]; vertex_y[i] := tmp; end; function clockwise( i, j : integer) : boolean ; (* returns true if vertex[i] is clockwise to vertex[j] relative to vertex[1] *) var i_x, i_y, j_x, j_y , cross: integer; begin (* first calculate position relative to first vertex *) i_x := vertex_x[i] - vertex_x[1]; i_y := vertex_y[i] - vertex_y[1]; j_x := vertex_x[j] - vertex_x[1]; j_y := vertex_y[j] - vertex_y[1]; (* now compute whether i is clockwise to j *) (* instead of comparing the polar angle directly, *) (* we can compare the cross-product of the vectors *) cross := (i_x * j_y) - (i_y * j_x); if cross = 0 then begin (* take closer vertex *) if abs(i_y) < abs(j_y) then begin clockwise := true; end else begin clockwise := false; end; end else if cross > 0 then begin clockwise := true; end else begin clockwise := false; end; end; (* ret 1 = straddle, -1 = no straddle, 0 = query point on polygon *) function straddle( i, j, k, l : integer) : integer; var x1, x2, x3, x4, y1, y2, y3, y4: integer; ki_x, ki_y, ji_x, ji_y, li_x, li_y : integer; ki_ji_cross, li_ji_cross : integer; (* l is the query point *) begin (* check bounding rectangles *) x1 := min(vertex_x[i], vertex_x[j]); x2 := max(vertex_x[i], vertex_x[j]); y1 := min(vertex_y[i], vertex_y[j]); y2 := max(vertex_y[i], vertex_y[j]); x3 := min(vertex_x[k], vertex_x[l]); x4 := max(vertex_x[k], vertex_x[l]); y3 := min(vertex_y[k], vertex_y[l]); y4 := max(vertex_y[k], vertex_y[l]); if (x2 >= x3) and (x4 >= x1) and (y2 >= y3) and (y4 >= y1) then begin (* check straddle with cross product test *) (* test k-i x j-i and l-i x j-i *) ki_x := vertex_x[k] - vertex_x[i]; ki_y := vertex_y[k] - vertex_y[i]; ji_x := vertex_x[j] - vertex_x[i]; ji_y := vertex_y[j] - vertex_y[i]; li_x := vertex_x[l] - vertex_x[i]; li_y := vertex_y[l] - vertex_y[i]; ki_ji_cross := (ki_x * ji_y) - (ki_y * ji_x); li_ji_cross := (li_x * ji_y) - (li_y * ji_x); if (ki_ji_cross = 0) or (li_ji_cross = 0) then begin (* verify point lies on segment *) if (x2 >= vertex_x[l]) and (vertex_x[l] >= x1) and (y2 >= vertex_y[l]) and (vertex_y[l] >= y1) then begin straddle := 0; end else begin straddle := 1; end; end else if (((ki_ji_cross > 0) and (li_ji_cross > 0)) or ((ki_ji_cross < 0) and (li_ji_cross < 0))) then begin straddle := -1; end else begin straddle := 1; end; end else begin straddle := -1; end; end; begin (* ---- read query point & vertices ---- *) while not eof do begin vidx := 0; while not eoln do begin read(vertex_x[vidx], vertex_y[vidx]); { if not eoln then begin read(c); while not eoln and (c <> ';') do begin read(c); end; end; } vidx := vidx + 1; end; readln; vidx := vidx - 1; (* ---- order vertices of polygon clockwise ---- *) (* start with bottom vertex *) for j := 2 to vidx do begin if (vertex_y[j] = vertex_y[1]) then begin if (vertex_x[j] < vertex_x[1]) then begin swap(j,1); end end else if vertex_y[j] < vertex_y[1] then begin swap(j,1); end; end; (* bubble sort vertices according to polar angle from bottom vertex *) (* yields the convex hull in clockwise order *) for i := 2 to vidx-1 do begin for j := vidx downto i+1 do begin if clockwise(j-1,j) then begin swap(j,j-1); end; end; end; (* ---- find center of polygon ---- *) center_x := 0; center_y := 0; for i := 1 to vidx do begin center_x := center_x + vertex_x[i]; center_y := center_y + vertex_y[i]; end; center_x := center_x div vidx; center_y := center_y div vidx; vertex_x[vidx+2] := center_x; vertex_y[vidx+2] := center_y; (* ---- check whether inside polygon ---- *) (* see whether line from center to query point *) (* passes through any edges of convex hull *) vertex_x[vidx+1] := vertex_x[1]; vertex_y[vidx+1] := vertex_y[1]; done := false; i := 1; while (not done) and (i < vidx+1) do begin cond := straddle(i,i+1,vidx+2,0); if (cond = 1) then begin writeln(vertex_x[0]:1, ' ', vertex_y[0]:1, ' outside'); done := true; end else if (cond = 0) then begin writeln(vertex_x[0]:1, ' ', vertex_y[0]:1, ' boundary'); done := true; end; i := i + 1; end; if not done then begin writeln(vertex_x[0]:1, ' ', vertex_y[0]:1, ' inside'); end; end; end.