program checkGhostbusters(input, output); const MAX_GHOSTS = 100; type spot = record x : integer; y : integer; end; spot_arr = array[1..MAX_GHOSTS] of spot; type Line = record x1, y1, x2, y2 : integer; end; LineA = array[0..MAX_GHOSTS-1] of Line; var lines : LineA; ghosts : spot_arr; busters : spot_arr; num : integer; correct : boolean; function min(x,y:integer) : integer; begin if (x < y) then min := x else min := y end; function max(x,y:integer) : integer; begin if (x > y) then max := x else max := y end; procedure read_arrs; var i : integer; begin readln(num); for i:= 1 to num do begin readln(ghosts[i].x, ghosts[i].y); end; for i:= 1 to num do begin readln(busters[i].x, busters[i].y); end; end; procedure read_pairs; var n,i : integer; begin readln(n); if (n <> num) then begin writeln('Wrong number of pairs!'); correct := false; end; for i:= 0 to num-1 do begin readln(lines[i].x1, lines[i].y1, lines[i].x2, lines[i].y2) end; end; function straddle( i, j : 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; begin (* check bounding rectangles *) x1 := min(lines[i].x1 , lines[i].x2 ); x2 := max(lines[i].x1 , lines[i].x2 ); y1 := min(lines[i].y1 , lines[i].y2 ); y2 := max(lines[i].y1 , lines[i].y2 ); x3 := min(lines[j].x1 , lines[j].x2 ); x4 := max(lines[j].x1 , lines[j].x2 ); y3 := min(lines[j].y1 , lines[j].y2 ); y4 := max(lines[j].y1 , lines[j].y2 ); if (x2 >= x3) and (x4 >= x1) and (y2 >= y3) and (y4 >= y1) then begin (* check straddle with cross product test *) ki_x := lines[j].x1 - lines[i].x1 ; ki_y := lines[j].y1 - lines[i].y1 ; ji_x := lines[i].x2 - lines[i].x1 ; ji_y := lines[i].y2 - lines[i].y1 ; li_x := lines[j].x2 - lines[i].x1 ; li_y := lines[j].y2 - lines[i].y1 ; 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 >= lines[j].x2 ) and (lines[j].x2 >= x1) and (y2 >= lines[j].y2 ) and (lines[j].y2 >= 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; procedure check; var i,j : integer; begin for i:= 0 to num-1 do begin for j:= i+1 to num-1 do begin if (straddle(i,j) = 1) and (straddle(j,i) = 1) then begin correct := false; writeln('CROSS: ', lines[i].x1:0, ',', lines[i].y1:0, '-', lines[i].x2:0, ',', lines[i].y2:0, ' and ', lines[j].x1:0, ',', lines[j].y1:0, '-', lines[j].x2:0, ',', lines[j].y2:0) end; end; end; end; procedure match_pairs; var i,j : integer; found : boolean; begin for i:= 0 to num-1 do begin found := false; for j:= 1 to num do begin if (ghosts[j].x = lines[i].x1) and (ghosts[j].y = lines[i].y1) then begin ghosts[j].x := -1; ghosts[j].y := -1; found := true; end; end; if not found then begin writeln('Ghost ', lines[i].x1, lines[i].y1, ' not in input'); correct := false; end; found := false; for j:= 1 to num do begin if (busters[j].x = lines[i].x2) and (busters[j].y = lines[i].y2) then begin busters[j].x := -1; busters[j].y := -1; found := true; end; end; if not found then begin writeln('Ghostbuster ', lines[i].x2, lines[i].y2, ' not in input'); correct := false; end; end; end; begin correct := true; read_arrs; (* get original input *) read_pairs; (* get pairings as line segments *) check; (* make sure no pairs cross *) match_pairs; (* make sure pairs match original input *) if correct then writeln('Solution correct') end.