ZOJ 1081 Points Within 은 다각형 내 에 있 는 지 판단 합 니 다.

문 제 는 매우 간단 하 다. 바로 다각형 과 점 을 제시 하여 이 점 들 이 제 시 된 다각형 안에 있 는 지 아 닌 지 를 판단 하 는 것 이다.
방법:
방사선 L 과 다각형 의 교점 을 계산 할 때 1.다각형 의 수평 변 에 대해 고려 하지 않 는 다.2。다각형 의 정점 과 L 이 교차 하 는 경우 이 정점 이 자신 이 속 한 변 의 세로 좌표 가 비교적 큰 정점 이 라면 계산 하고 그렇지 않 으 면 무시 합 니 다.3。P 가 다각형 가장자리 에 있 는 경우 P 가 다각형 줄 에 속 하 는 지 직접 판단 할 수 있 습 니 다.교점 개수 가 홀수 라면 다각형 안에 있 고 그렇지 않 으 면 없다.이로부터 알고리즘 의 위조 코드 는 다음 과 같다.   count ← 0;     P 를 단점 으로 하여 오른쪽 에서 왼쪽으로 방사선 L 을 만 듭 니 다.      for 다각형 의 각 변 s     do if P 는 사 이 드 s 에 있어 요.            then return true;         if s 수준 아니에요.          then if s 의 한 점 은 L 에 있 습 니 다.                if 이 점 은 s 양 끝 점 중 세로 좌표 가 비교적 큰 점 이다.                  then count ← count+1               else if s 와 L 이 교차 합 니 다.                then count ← count+1;     if count mod 2 = 1        then return true;     else return false; 그 중에서 방사선 L 을 만 드 는 방법 은 P '의 세로 좌 표를 P 와 같 고 가로 좌 표를 정 무한대 (큰 정수) 로 설정 하면 P 와 P' 가 방사선 L 을 확정 하 는 것 이다.

var
  n,tot,m,i,p,q:longint;
  x,y:array[1..100] of longint;

function max(x,y:longint):longint;
begin
  if x>y then exit(x)
         else exit(y);
end;

function min(x,y:longint):longint;
begin
  if x<y then exit(x)
         else exit(y);
end;

function pd(p,q:longint):boolean;
var
  p1,q1,sum,s,i,s1:longint;
begin
  p1:=maxlongint div 200000;
  q1:=q;
  sum:=0;
  for i:=1 to n do
  begin
    s:=(x[i]-x[i+1])*(q-y[i+1])-(p-x[i+1])*(y[i]-y[i+1]);
    if (s=0)and(p<=max(x[i],x[i+1]))and(p>=min(x[i],x[i+1]))and(q<=max(y[i],y[i+1]))and(q>=min(y[i],y[i+1])) then exit(true);
    if y[i]=y[i+1] then continue;
    s:=(p1-p)*(y[i]-q)-(q1-q)*(x[i]-p);
    if (s=0)and(x[i]<=max(p,p1))and(x[i]>=min(p,p1))and(y[i]<=max(q,q1))and(y[i]>=min(q,q1)) then
    begin
      if y[i]>y[i+1] then inc(sum);
      continue;
    end;
    s:=(p1-p)*(y[i+1]-q)-(q1-q)*(x[i+1]-p);
    if (s=0)and(x[i+1]<=max(p,p1))and(x[i+1]>=min(p,p1))and(y[i+1]<=max(q,q1))and(y[i+1]>=min(q,q1)) then
    begin
      if y[i+1]>y[i] then inc(sum);
      continue;
    end;
    s:=(p1-p)*(y[i]-q)-(q1-q)*(x[i]-p);
    s1:=(p1-p)*(y[i+1]-q)-(q1-q)*(x[i+1]-p);
    if s*s1>0 then continue;
    s:=(x[i+1]-x[i])*(q-y[i])-(y[i+1]-y[i])*(p-x[i]);
    s1:=(x[i+1]-x[i])*(q1-y[i])-(y[i+1]-y[i])*(p1-x[i]);
    if s*s1>0 then continue;
    inc(sum);
  end;
  if sum mod 2=0
    then exit(false)
    else exit(true);
end;

begin
  read(n);
  while n>0 do
  begin
    if tot>0 then writeln;
    inc(tot);
    writeln('Problem ',tot,':');
    readln(m);
    for i:=1 to n do
      readln(x[i],y[i]);
    x[n+1]:=x[1];
    y[n+1]:=y[1];
    for i:=1 to m do
    begin
      readln(p,q);
      if pd(p,q)
        then writeln('Within')
        else writeln('Outside');
    end;
    read(n);
  end;
end.