안티앨리어싱
시간 제한4초메모리 제한1024 MB
볼록 다각형과 픽셀 위치가 주어질 때, 픽셀 넓이 중 다각형 안에 포함되는 비율을 기약분수로 구합니다.
문제
폴리곤의 계단 현상(에일리어싱) 효과를 줄이기 위해 컴퓨터 그래픽스 시스템은 각 픽셀의 밝기를 그 픽셀 안에서 폴리곤 내부에 속하는 면적에 비례하도록 설정하여 폴리곤을 그린다. 픽셀이 폴리곤 안에 완전히 들어가면 그 픽셀은 가장 밝은 값으로 설정된다. 픽셀의 절반만 폴리곤 안에 들어가면 그 픽셀은 가장 어두운 값과 가장 밝은 값의 중간으로 설정된다.
볼록 다각형과 픽셀 위치가 주어졌을 때, 픽셀 면적 중 다각형 안에 포함되는 비율을 구하라. 각 픽셀은 정사각형이며 행 번호 과 열 번호 로 식별된다. 다각형의 꼭짓점이 에 있으면, 그 꼭짓점은 행 , 열 픽셀의 중심에 놓인다. 행은 맨 위 행을 으로 하여 부터 번호가 매겨지고, 열은 가장 왼쪽 열을 으로 하여 부터 번호가 매겨진다.
입력
첫 줄에 두 정수 ()과 ()이 주어진다. 은 볼록 다각형의 꼭짓점 개수이고, 는 질의 개수이다. 다음 개 줄에는 반시계 방향으로 나열된 다각형 꼭짓점의 좌표 , 가 한 줄에 하나씩 주어진다. 다음 개 줄에는 관심 있는 픽셀의 좌표 , 가 한 줄에 하나씩 주어진다. 다각형의 넓이는 양수임이 보장된다. 모든 좌표는 , 을 만족한다.
출력
각 질의에 대해, 픽셀 면적 중 다각형 안에 포함되는 비율을 기약분수로 한 줄에 출력한다.