9.9 NOIP模拟题
T1 两个圆的面积求并
/* 计算圆的面积并 多个圆要用辛普森积分解决 这里只有两个，模拟计算就好 两圆相交时，面积并等于中间两个扇形面积减去两个三角形面积 余弦定理求角度，算出三角形面积 */ #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const double PI=3.14159265358979323846264; struct node{double x,y;double r; }a[2]; inline double getdis(node b,node c){double xx=b.x-c.x;double yy=b.y-c.y;return sqrt(xx*xx+yy*yy); }void deal(node b,node c) {double len=getdis(b,c);if(len<=fabs(b.r-c.r)){if(b.r<c.r) swap(b,c);double t1=PI*b.r*b.r;printf("%.3lf\n",t1);return ;}double L=b.r+c.r;double t1=PI*b.r*b.r;double t2=PI*c.r*c.r;if(L<=len){printf("%.3lf\n",t1+t2);return ;}double ang1=acos((b.r*b.r+len*len-c.r*c.r)/2.0/b.r/len); double ang2=acos((c.r*c.r+len*len-b.r*b.r)/2.0/c.r/len);double ret=ang1*b.r*b.r+ang2*c.r*c.r-len*b.r*sin(ang1); printf("%.3lf\n",t1+t2-ret); }int main() {freopen("standing.in","r",stdin);freopen("standing.out","w",stdout);int T;scanf("%d",&T);while(T--){scanf("%lf%lf%lf%lf%lf%lf",&a[0].x,&a[0].y,&a[0].r,&a[1].x,&a[1].y,&a[1].r);deal(a[0],a[1]);}return 0; }
T2 约瑟夫问题
/* 其实也就是建好线段树 然后查找第m+1个数的位置，然后把这个位置到根的路径都-1. */ #include<cstdio> #include <iostream> #define N 100007using namespace std; struct SegTree {int l,r,m;int num; }; SegTree ltree[N<<2]; int n,m,ln;int ans[N];void init(int nowat, int tl, int tr) {ltree[nowat].l=tl;ltree[nowat].r=tr;ltree[nowat].m=(tl+tr)>>1;ltree[nowat].num=tr-tl+1;if(tl<tr){init(nowat*2,tl,ltree[nowat].m);init(nowat*2+1,ltree[nowat].m+1,tr);} }void del(int nowat, int tw) {--ltree[nowat].num;if (ltree[nowat].l<ltree[nowat].r){if (tw<=ltree[nowat].m) del(nowat*2,tw);else del(nowat*2+1,tw);} }int findcode(int tcode) {int i=1;int sum=0;while (ltree[i].l<ltree[i].r){if(sum+ltree[i+i].num<tcode){sum+=ltree[i+i].num;i=i+i+1;}else i=i+i;}return ltree[i].r; }int main() {freopen("resist.in","r",stdin);freopen("resist.out","w",stdout);scanf("%d%d",&n,&m);ln=0;init(1,1,n);int i,j,k=0;int num=0;for (i=1;i<=n;++i){k=(k+m-1)%(n-i+1);j=findcode(k+1);ans[++num]=j;del(1, j);if (i!=n)k=k%(n-i);}printf("%d\n",ans[num]);fclose(stdin);fclose(stdout);return 0; }
T3 给你矩阵的正视图和左视图中每个点的值 让你求俯视图和的范围
/* 最大值好求 最小值就是行和列出现同一个数后 那个出现次数多的出现的次数乘上这个数 */ #include<iostream> #include<cstdio> #include<cstring>const int N=1e3+10; using namespace std; int n,m,H[N],L[N],ans2,ans1; int f[N],c[N];int main() {freopen("neighbor.in","r",stdin);freopen("neighbor.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1; i<=n; i++)scanf("%d",&H[i]);for(int i=1; i<=m; i++)scanf("%d",&L[i]);for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)ans2+=min(H[i],L[j]);for(int i=1; i<=n; i++)f[H[i]]++;for(int i=1; i<=m; i++)c[L[i]]++;for(int i=0; i<=1000; i++) ans1+=max(f[i],c[i])*i;printf("%d %d\n",ans1,ans2);return 0; }