【tyvj1360】Imperishable Shooting

2014年5月25日2,1580

背景 Background

如果您不想看这个扯淡的背景,可以直接移步Hint,有简洁版。。。

一天,蓬莱の魚の形误闯了迷途森林,于是光荣地迷路了。。此时,一个白发红眼的少女出现了。。
少女:你迷路了吗?
蓬莱の魚の形:。。是。。
少女:你叫什么名字?
蓬莱の魚の形:蓬莱の魚の形。。
少女(仔细打量其一番):本来还准备帮你的,但是一想到一个妖怪鱼有这个名字。。。就让我看看你有多大本事吧!(突然从背后扇动出熊熊燃烧的翅膀)「Imperishable Shooting」!
蓬莱の魚の形:啊啊啊~~

描述 Description

蓬莱の魚の形的能力是可以事先选好一些点做好魔法阵,在对方每一波弹幕展开前可以瞬间跳跃到一个魔法阵中。但是,如果三个魔法阵在同一条直线上,就会出现干扰,而消失作用,蓬莱の魚の形当然不会犯这种低级错误。而根据蓬莱の魚の形多年玩永夜抄的经验,「Imperishable shooting」的弹幕是一个个多边形,而这些多边形的顶点都在蓬莱の魚の形做的魔法阵上(难道是因为这样威力更大?),然后弹幕会以鱼眼无法企及的速度散开,只要在这多边形外面,就一定会被打中。于是蓬莱の魚の形在每次多边形展开之前,会跳跃到多边形内部的魔法阵中。但是他想知道,每次他有多少个魔法阵可以选择。当然,如果蓬莱の魚の形在某一波中无论如何也躲不过,那么只好杯具地miss然后重生了(为啥这家伙也有重生的能力- -)。

输入格式 InputFormat

输入格式
第一行n表示蓬莱の魚の形制作了n个魔法阵。
后面n行每行两个整数xi,yi,表示第i个魔法阵的坐标为(xi,yi)。(数据保证没有两个魔法阵位置相同,没有三个魔法阵在同一条直线上)
然后是m表示「Imperishable shooting」依次有m波多边形弹幕。
下面2m行每两行的第一行有一个数s,表示这一波弹幕是s边形,下面一行有s个数,表示按顺时针顺序或逆时针顺序的多边形顶点所在魔法阵的编号(编号为0到n-1,多边形可能是凹的,不确定顺时针还是逆时针)。

输出格式 OutputFormat

输出格式
m行,对于每波弹幕,输出蓬莱の魚の形有多少个魔法阵可以选择。特别的,如果蓬莱の魚の形在某一波无论如何都躲不过去,这一行就输出”Miss!”(不包括引号)。

样例输入 SampleInput [复制数据]

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint

数据范围
n<=1000
m<=10000
s<=100
-10000<=x,y<=10000
提示:由于数据比较大,建议使用C++的童鞋们使用stdio来读入和输出。

题目描述简洁版:给出平面上n个点,保证无三点共线,再给出m个多边形(可能是凹多边形),求每个多边形内部包含的点的个数(特别的,如果结果是0的话请输出”Miss!”,不包含引号)。

来源 Source

蓬莱の魚の形(其实还有个网名叫小小鱼。。)

后记:蓬莱の魚の形最终败倒在少女脚下,被她红烧,虽说死不了,但是有多么悲剧大家都明白。。。

题解
此题似乎非常的优越啊。。。
按照题解君的解法,因为题目中不存在三点共线的情况
先设p0(-10000,-10000),然后将其他点极角排序(如果用最左下的点后面计算时还需要特殊处理)
f[i][j]表示0,i,j这个三角形内的点数,ij为排序后的标号
这一步可以预处理,做法是对于每个i建一棵平衡树,将排在它以后的j逐个加入平衡树,平衡树的关键字为i为基点的极角,可以发现j在平衡树中的排名就是三角形内部的点数+1
然后将三角形内部的点数当做其面积,用叉乘求多边形面积的方法计算内部总点数,再将边上额外计算的点减掉,可以发现,没有减去的点数等于顺时针的边数-1
总复杂度O(n^2logn + m*s)
平衡树不用额外写一个函数查询排名,在插入的时候顺便查询下即可
ans<=0输出miss
发现加了inline从530ms-300ms