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