9.9 NOIP模拟题

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[];

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[].x,&a[].y,&a[].r,&a[].x,&a[].y,&a[].r);

        deal(a[],a[]);

    }

    return ;

}

T2 约瑟夫问题

/*

其实也就是建好线段树

然后查找第m+1个数的位置，然后把这个位置到根的路径都-1.

*/

#include<cstdio>

#include <iostream>

#define N 100007

using namespace std;

struct SegTree

{

    int l,r,m;

    int num;

};

SegTree ltree[N<<];

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)>>;

    ltree[nowat].num=tr-tl+;

    if(tl<tr)

    {

        init(nowat*,tl,ltree[nowat].m);

        init(nowat*+,ltree[nowat].m+,tr);

    }

}

void del(int nowat, int tw)

{

    --ltree[nowat].num;

    if (ltree[nowat].l<ltree[nowat].r)

    {

        if (tw<=ltree[nowat].m) del(nowat*,tw);

        else del(nowat*+,tw);

    }

}

int findcode(int tcode)

{

    int i=;

    int sum=;

    while (ltree[i].l<ltree[i].r)

    {

        if(sum+ltree[i+i].num<tcode)

        {

            sum+=ltree[i+i].num;

            i=i+i+;

        }

        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=;init(,,n);

    int i,j,k=;int num=;

    for (i=;i<=n;++i)

    {

        k=(k+m-)%(n-i+);

        j=findcode(k+);ans[++num]=j;

        del(, j);

        if (i!=n)k=k%(n-i);

    }

    printf("%d\n",ans[num]);

    fclose(stdin);fclose(stdout);

    return ;

}

T3 给你矩阵的正视图和左视图中每个点的值   让你求俯视图和的范围

/*

最大值好求

最小值就是行和列出现同一个数后

那个出现次数多的出现的次数乘上这个数

*/

#include<iostream>

#include<cstdio>

#include<cstring>

const int N=1e3+;

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=; i<=n; i++)scanf("%d",&H[i]);

    for(int i=; i<=m; i++)scanf("%d",&L[i]);

    for(int i=; i<=n; i++)

        for(int j=; j<=m; j++)

            ans2+=min(H[i],L[j]);

    for(int i=; i<=n; i++)f[H[i]]++;

    for(int i=; i<=m; i++)c[L[i]]++;

    for(int i=; i<=; i++) ans1+=max(f[i],c[i])*i;

    printf("%d %d\n",ans1,ans2);

    return ;

}