当前位置：首页 > news >正文

打卡信奥刷题（3091）用C++实现信奥题 P7133 小 P 的星空

news 2026/6/2 21:37:26

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 想知道，每一次转动过程中他最多可以让多少星星出现在他正前方（包括转动初始方向和结束方向正前方看到的星星）。

输入格式

总共包括n+m+1n+m+1n+m+1行。

第一行包含两个正整数n,mn,mn,m，分别表示星星颗数和转动次数。

接下来的nnn行，每行两个整数xi,yix_i,y_ixi,yi。

接下来的mmm行，每行两个整数ui,viu_i,v_iui,vi，意义如【题目描述】中所述。

每行的两个数字间由单个空格隔开，数据为 Linux 格式，行末保证没有多余空格。

输出格式

mmm行，每行一个整数。第iii行的整数表示第iii次转动的答案。

输入输出样例 #1

输入 #1

5 2 1 0 1 1 2 2 -1 2 -2 -1 -1 1 -1 2

输出 #1

4 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++实现

#include<bits/stdc++.h>usingnamespacestd;doublec1[100005],c2[100005],d1[100005],d2[100005];doublepi=acos(-1);intmain(){intn,m;cin>>n>>m;for(inti=1;i<=n;i++){intx,y;scanf("%d%d",&x,&y);c1[i]=acos(1.0*x/sqrt(1.0*x*x+1.0*y*y));if(y<0)c1[i]=2*pi-c1[i];longlongtt=c1[i]*10000000000ll;c1[i]=1.0*tt/10000000000ll;}for(inti=1;i<=m;i++){intu,v;scanf("%d%d",&u,&v);c2[i]=acos(1.0*u/sqrt(1.0*u*u+1.0*v*v));if(v<0)c2[i]=2*pi-c2[i];longlongtt=c2[i]*10000000000ll;c2[i]=1.0*tt/10000000000ll;}sort(c1+1,c1+n+1);doublecc=0;for(inti=1;i<=m;i++){doubletc1=min(cc,c2[i]),tc2=max(cc,c2[i]);intwz1=lower_bound(c1+1,c1+n+1,tc1)-c1;intwz2=upper_bound(c1+1,c1+n+1,tc2)-c1;intans=wz2-wz1;wz1=upper_bound(c1+1,c1+n+1,tc1)-c1;wz2=lower_bound(c1+1,c1+n+1,tc2)-c1;ans=max(ans,n-wz2+wz1);printf("%d\n",ans);cc=c2[i];}return0;}