「JoyOI1360」Imperishable Shooting
背景 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!”（不包括引号）。
数据范围和注释 Hint
数据范围
n<=1000
m<=10000
s<=100
-10000<=x,y<=10000
提示：由于数据比较大，建议使用C++的童鞋们使用stdio来读入和输出。
题目描述简洁版：给出平面上n个点，保证无三点共线，再给出m个多边形（可能是凹多边形），求每个多边形内部包含的点的个数（特别的，如果结果是0的话请输出”Miss!”，不包含引号）。
来源 Source
蓬莱の魚の形（其实还有个网名叫小小鱼。。）
后记：蓬莱の魚の形最终败倒在少女脚下，被她红烧，虽说死不了，但是有多么悲剧大家都明白。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<ctime> using namespace std; //========================================= inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //========================================= 快速读入 int n,m,x,y; int root,sz,tmp,ans; int ls[1005],rs[1005],num[1005],s[1005],rnd[1005]; int b[1005],mark[1005]; int f[1005][1005]; struct point{int x,y,num;}p[1005]; //========================================= inline point sub(point a,point b) {point t;t.x=a.x-b.x;t.y=a.y-b.y;return t;} inline int cmul(point a,point b) {return a.x*b.y-a.y*b.x;} inline int turn(point a,point b,point c) {return cmul(sub(c,a),sub(b,a));} inline int sqr(int x){return x*x;} inline int dis(point a,point b) {return sqr(a.x-b.x)+sqr(a.y-b.y);} inline bool cmp(point a,point b) {return turn(p[0],a,b)==0?dis(a,p[0])<dis(b,p[0]):turn(a,p[0],b)>0;} //========================================= 计算几何 void update(int k) {s[k]=s[ls[k]]+s[rs[k]]+1;} void rturn(int &k) {int t=ls[k];ls[k]=rs[t];rs[t]=k;s[t]=s[k];update(k);k=t;} void lturn(int &k) {int t=rs[k];rs[k]=ls[t];ls[t]=k;s[t]=s[k];update(k);k=t;} void insert(int &k,int id) { if(!k) { k=++sz; s[k]=1;ls[k]=rs[k]=0; num[k]=id;rnd[k]=rand(); return; } s[k]++; if(turn(p[x],p[num[k]],p[id])>0) { insert(ls[k],id); if(rnd[ls[k]]<rnd[k])rturn(k); } else { insert(rs[k],id); tmp+=s[ls[k]]+1; if(rnd[rs[k]]<rnd[k])lturn(k); } } //========================================= 平衡树 void pre() { sort(p+1,p+n+1,cmp); for(int i=1;i<=n;i++) mark[p[i].num]=i; for(x=1;x<n;x++) { root=sz=0; for(y=x+1;y<=n;y++) { tmp=0; insert(root,y); f[x][y]=tmp; f[y][x]=tmp; } } } void getans() { int e=read(); for(int i=1;i<=e;i++) b[i]=read(),b[i]++,b[i]=mark[b[i]]; b[e+1]=b[1]; ans=tmp=0; for(int i=1;i<=e;i++) if(turn(p[0],p[b[i]],p[b[i+1]])>0) ans+=f[b[i]][b[i+1]]; else {ans-=f[b[i]][b[i+1]];tmp++;} if(ans<0)ans=-ans,tmp=e-tmp; ans=ans-tmp+1; if(ans<=0)puts("Miss!"); else printf("%d\n",ans); } int main() { n=read(); p[0].x=-10000;p[0].y=-10000; for(int i=1;i<=n;i++) p[i].x=read(),p[i].y=read(),p[i].num=i; pre(); m=read(); for(int i=1;i<=m;i++) getans(); return 0; } |
OI 课件=>
