P7133 小 P 的星空题目背景星依云渚溅溅露零玉液涓涓宝砌哀兰剪剪。碧天如练光摇北斗阑干。—— 【元】孟昉《天净沙 · 星依云渚溅溅》小 P 漫步于星空之下。“摘下星星送给你你就是我的全世界”。“今夜我不关心人类我只想你”。题目描述将星空看作一个平面直角坐标系小 P 所在的位置为(0,0)(0,0)(0,0)即坐标原点。天上共有nnn颗星星第iii颗星星的坐标为(xi,yi)(x_i,y_i)(xi​,yi​)。小 P 最初面向点(1,0)(1,0)(1,0)然后小 P 会进行mmm次原地转动第iii次转动后会面向点(ui,vi)(u_i,v_i)(ui​,vi​)。他可以选择逆时针转动或顺时针转动当面向此次旋转最终将要面向的方向时此次转动立即停止。他相信在转动过程中越多的星星出现在他正前方他【数据删除】。小 P 想知道每一次转动过程中他最多可以让多少星星出现在他正前方包括转动初始方向和结束方向正前方看到的星星。输入格式总共包括nm1nm1nm1行。第一行包含两个正整数n,mn,mn,m分别表示星星颗数和转动次数。接下来的nnn行每行两个整数xi,yix_i,y_ixi​,yi​。接下来的mmm行每行两个整数ui,viu_i,v_iui​,vi​意义如【题目描述】中所述。每行的两个数字间由单个空格隔开数据为 Linux 格式行末保证没有多余空格。输出格式mmm行每行一个整数。第iii行的整数表示第iii次转动的答案。输入输出样例 #1输入 #15 2 1 0 1 1 2 2 -1 2 -2 -1 -1 1 -1 2输出 #14 5输入输出样例 #2输入 #2见下发文件 ex_star2.in输出 #2见下发文件 ex_star2.out输入输出样例 #3输入 #3见下发文件 ex_star3.in输出 #3见下发文件 ex_star3.out说明/提示样例1示意图如下橙色点为星星绿色点小 P 第一次的转动位置。第一次转动从(1,0)(1,0)(1,0)转到(−1,1)(-1,1)(−1,1)。若顺时针转动(蓝色区域包括边界)(1,0)(1,0)(1,0),(−2,−1)(-2,-1)(−2,−1)共计222颗星星而逆时针转动(绿色区域包括边界)(1,0)(1,0)(1,0),(1,1)(1,1)(1,1),(2,2)(2,2)(2,2),(−1,2)(-1,2)(−1,2)共计444颗星星。第二次转动从(−1,1)(-1,1)(−1,1)转到(−1,2)(-1,2)(−1,2)逆时针转动555颗星星都会在转动过程中出现在小 P 正前方。除测试点242424和252525外其他测试点保证所有坐标的绝对值≤1000\le 1000≤1000。对于前121212个测试点保证原点到任意星星形成的射线上没有其他星星。除23,2523,2523,25测试点外对于所有编号为奇数的测试点保证小 P 初始面向方向和每次转动目标方向上没有任何星星。除22,2422,2422,24测试点外对于所有编号为偶数的测试点保证小 P 初始面向方向和每次转动目标方向上至少有一颗星星。对于100%100\%100%的数据保证星星的坐标互不相同保证坐标不会出现(0,0)(0,0)(0,0)保证不会出现转动初始方向等于结束方向。样例333满足偶数测试点的限制。C实现#includebits/stdc.husingnamespacestd;doublec1[100005],c2[100005],d1[100005],d2[100005];doublepiacos(-1);intmain(){intn,m;cinnm;for(inti1;in;i){intx,y;scanf(%d%d,x,y);c1[i]acos(1.0*x/sqrt(1.0*x*x1.0*y*y));if(y0)c1[i]2*pi-c1[i];longlongttc1[i]*10000000000ll;c1[i]1.0*tt/10000000000ll;}for(inti1;im;i){intu,v;scanf(%d%d,u,v);c2[i]acos(1.0*u/sqrt(1.0*u*u1.0*v*v));if(v0)c2[i]2*pi-c2[i];longlongttc2[i]*10000000000ll;c2[i]1.0*tt/10000000000ll;}sort(c11,c1n1);doublecc0;for(inti1;im;i){doubletc1min(cc,c2[i]),tc2max(cc,c2[i]);intwz1lower_bound(c11,c1n1,tc1)-c1;intwz2upper_bound(c11,c1n1,tc2)-c1;intanswz2-wz1;wz1upper_bound(c11,c1n1,tc1)-c1;wz2lower_bound(c11,c1n1,tc2)-c1;ansmax(ans,n-wz2wz1);printf(%d\n,ans);ccc2[i];}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容