Girlfriend

#include<iostream>
#include<cstring>
#include<cmath>

using namespace std;

const double pi=acos(-1);

int T;
double x1,_y1,z1;
double x2,y2,z2;
double x3,y3,z3;
double x4,y4,z4;
double k1,k2;

void solve(double x1,double y1,double z1,double r1,double x2,double y2,double z2,double r2){
    double ans=0;
    //球心距离 
    double dis=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
    //相离或相切 
    if(dis>=r1+r2){
        ans=0;
    }
    //内含或内切 
    else if (dis+r1<=r2){
        ans=(4.00/3.00)*pi*r1*r1*r1;
    }
    else if(dis+r2<=r1){
        ans=(4.00/3.00)*pi*r2*r2*r2;
    }
    //相交 
    else{
        double cal=(r1*r1+dis*dis-r2*r2)/(2.00*dis*r1);
        double h=r1*(1-cal);
        ans+=(1.00/3.00)*pi*(3.00*r1-h)*h*h;
        cal=(r2*r2+dis*dis-r1*r1)/(2.00*dis*r2);
        h=r2*(1.00-cal);
        ans+=(1.00/3.00)*pi*(3.00*r2-h)*h*h;
    }
    printf("%.3f\n",ans);
}

int main(){
    cin.tie(0);
    cin>>T;
    while(T--){
        cin>>x1>>_y1>>z1;
        cin>>x2>>y2>>z2;
        cin>>x3>>y3>>z3;
        cin>>x4>>y4>>z4;
        cin>>k1>>k2; 

        //circle - 1
        double a1,b1,c1,d1,e1,r1;
        double cx1,cy1,cz1;
        a1=1-k1*k1;
        b1=2*k1*k1*x2-2*x1;
        c1=2*k1*k1*y2-2*_y1;
        d1=2*k1*k1*z2-2*z1;
        e1=x1*x1+_y1*_y1+z1*z1-k1*k1*(x2*x2+y2*y2+z2*z2);
        cx1=(k1*k1*x2-x1)/(k1*k1-1);
        cy1=(k1*k1*y2-_y1)/(k1*k1-1);
        cz1=(k1*k1*z2-z1)/(k1*k1-1);
        r1=sqrt((b1*b1+c1*c1+d1*d1)/(4*a1*a1)-e1/a1);

        //circle - 2

        double a2,b2,c2,d2,e2,r2;
        double cx2,cy2,cz2;
        a2=1-k2*k2;
        b2=2*k2*k2*x4-2*x3;
        c2=2*k2*k2*y4-2*y3;
        d2=2*k2*k2*z4-2*z3;
        e2=x3*x3+y3*y3+z3*z3-k2*k2*(x4*x4+y4*y4+z4*z4);
        cx2=(k2*k2*x4-x3)/(k2*k2-1);
        cy2=(k2*k2*y4-y3)/(k2*k2-1);
        cz2=(k2*k2*z4-z3)/(k2*k2-1);
        r2=sqrt((b2*b2+c2*c2+d2*d2)/(4*a2*a2)-e2/a2);

//        printf("case: \n");
//        printf("circle1 = (%lf,%lf,%lf) -- %lf\n",cx1,cy1,cz1,r1);
//        printf("circle2 = (%lf,%lf,%lf) -- %lf\n",cx2,cy2,cz2,r2);
        solve(cx1,cy1,cz1,r1,cx2,cy2,cz2,r2);
    }
}

Penguins

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N=25;

char mpl[N][N],mpr[N][N];
char op[N][N][N][N];
int d[N][N][N][N];
int dirl[4][2]={1,0,0,-1,0,1,-1,0};
int dirr[4][2]={1,0,0,1,0,-1,-1,0};
char dir[]="DLRU";
pair<PII,PII> lst[N][N][N][N];

vector<char> ans;

void check1(int &x1,int &y1,int k){
    int x2=x1+dirl[k][0];
    int y2=y1+dirl[k][1];
    if(x2<1||x2>20||y2<1||y2>20||mpl[x2][y2]=='#'){
        x2=x1;
        y2=y1;
    }
    x1=x2;
    y1=y2;
}

void check2(int &x3,int &y3,int k){
    int x4=x3+dirr[k][0];
    int y4=y3+dirr[k][1];
    if(x4<1||x4>20||y4<1||y4>20||mpr[x4][y4]=='#'){
        x4=x3;
        y4=y3;
    }
    x3=x4;
    y3=y4;
}

void bfs(){
    queue<pair<PII,PII>> q;
    q.push({{20,20},{20,1}});
    memset(d,-1,sizeof d);
    op[20][20][20][1]='0';
    d[20][20][20][1]=0;
    while(!q.empty()){
        int x1=q.front().x.x,y1=q.front().x.y;
        int x2=q.front().y.x,y2=q.front().y.y;
        q.pop();
        for(int i=0;i<4;i++){
            int x3=x1,y3=y1;
            int x4=x2,y4=y2;
            check1(x3,y3,i);
            check2(x4,y4,i);
            if(d[x3][y3][x4][y4]!=-1)    continue;
            d[x3][y3][x4][y4]=d[x1][y1][x2][y2]+1;
            op[x3][y3][x4][y4]=dir[i];
            lst[x3][y3][x4][y4]={{x1,y1},{x2,y2}};
            q.push({{x3,y3},{x4,y4}});
            if(x3==1&&y3==20&&x4==1&&y4==1){
                return;
            }
        }
    }
}

int main(){
    for(int i=1;i<=20;i++){
        cin>>mpl[i]+1;
        cin>>mpr[i]+1;
    }
    bfs();
    int xa=1,ya=20,xb=1,yb=1;
    printf("%d\n",d[xa][ya][xb][yb]);
    while(1){
        ans.push_back(op[xa][ya][xb][yb]);
        mpl[xa][ya]='A';
        mpr[xb][yb]='A';
        int u=lst[xa][ya][xb][yb].x.x;
        int v=lst[xa][ya][xb][yb].x.y;
        int w=lst[xa][ya][xb][yb].y.x;
        int p=lst[xa][ya][xb][yb].y.y;
        xa=u,ya=v,xb=w,yb=p;
        if(d[xa][ya][xb][yb]==0){
            mpl[xa][ya]='A';
            mpr[xb][yb]='A';
            break;
        }
    }
    reverse(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++)    printf("%c",ans[i]);
    puts("");
    for(int i=1;i<=20;i++){
        printf("%s %s\n",mpl[i]+1,mpr[i]+1);
    }
}

//    while(1){
//        ans.push_back(op[xa][ya][xb][yb]);
//        mpl[xa][ya]='A';
//        mpr[xb][yb]='A';
//        int u=lst[xa][ya][xb][yb].first.first;
//        int v=lst[xa][ya][xb][yb].first.second;
//        int w=lst[xa][ya][xb][yb].second.first;
//        p=lst[xa][ya][xb][yb].second.second;
//        xa=u;ya=v;xb=w,yb=p;
//        if(d[xa][ya][xb][yb]==0){
//            mpl[xa][ya]='A';
//            mpr[xb][yb]='A';
//            break;
//        }
//    }

Stack

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N=1000010;

LL a[N],b[N],cnt[N];
LL stk[N],top;
bool vis[N];

int n,k;

int main(){
    scanf("%d%d",&n,&k);
    int p,x;
    while(k--){
        scanf("%d%d",&p,&x);
        vis[p]=true;
        cnt[p]=x;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            a[i]=1ll*i*1000010;
            stk[++top]=a[i];
        }
        else{
            if(cnt[i]>top+1){
                puts("-1");
                return 0;
            }
            else if(cnt[i]==top+1){
                a[i]=1ll*i*1000010;
                stk[++top]=a[i];
            }
            else{
                stk[cnt[i]]--;
                top=cnt[i];
                a[i]=stk[top];
            }
        }
    }
    for(int i=1;i<=n;i++)    b[i]=a[i];
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)    printf("%d ",lower_bound(b+1,b+n+1,a[i])-b);
}