#P1474. Fsheep

    ID: 486 传统题 1000ms 512MiB 尝试: 14 已通过: 2 难度: 6 上传者: 标签>CF2100提高点在多边形内二分查找叉积鞋带公式平方距离比较

Fsheep

题目描述

给定一个羊圈,其为星形多边形,让你判断一些点(其实就是羊)是否位于多边形内。

输入格式

第一行给出 N,MN,M 表示羊圈羊圈点的个数及羊的数目

接下来 NN 行,每行两个数 x,yx,y 描述羊圈的顶点,顶点沿多边形边界依次给出,可能为顺时针或逆时针方向。

接下来 MM 行,每行两个数 x,yx,y 描述羊的位置

输出格式

输出有 MM 行,对于每只羊如果在羊圈内输出 Good sheep,否则输出 Bad sheep

6 5
2 2
4 4
6 6
-3 1
-1 -1
5 1
2 1
3 2
6 6
3 3
-3 0
Good sheep
Bad sheep
Good sheep
Good sheep
Bad sheep

补充约定与数据范围

保证原点 (0,0)(0,0) 在多边形内部,并且从原点能看见多边形内部的全部位置(原点位于多边形的核内)。位于边界上的羊也算在羊圈内。

3≤N≤1053\le N\le10^5,0≤M≤1050\le M\le10^5。全部坐标都是整数,且绝对值不超过 10910^9。本地采用单组数据,并对每只羊分别输出判断结果。

本站数据约定

SPOJ FSHEEP 原题的原始格式、方向及数值范围与本站改编不同。本题以这里的单组、逐点输出格式为准;当前数据包含顺时针顶点和绝对值达到 10910^9 的坐标,故不应直接依赖原版的逆时针与 3200032000 范围。原点在核内及边界计入规则保持不变。