期望得分：20+100+100=220
实际得分：20+100+100=220
特判相离、内含
对于两圆相交的情况，一直在考虑求交点
实际上相交的面积可以用两个扇形减去两个三角形
正弦定理、余弦定理来搞搞
#include<cmath> #include<cstdio> #include<algorithm> using namespace std; const double pi=acos(-1.0); const double eps=1e-6; double Two_point_dis(double x1,double yy1,double x2,double yy2) { return sqrt((x1-x2)*(x1-x2)+(yy1-yy2)*(yy1-yy2)); } double circle_S(double r) { return pi*r*r; } int main() { freopen("standing.in","r",stdin); freopen("standing.ans","w",stdout); int T; scanf("%d",&T); double x1,yy1,r1,x2,yy2,r2; while(T--) { scanf("%lf%lf%lf%lf%lf%lf",&x1,&yy1,&r1,&x2,&yy2,&r2); double dis=Two_point_dis(x1,yy1,x2,yy2); if(dis>=r1+r2) { printf("%.3lf ",circle_S(r1)+circle_S(r2)); continue; } if(dis<=fabs(r1-r2)) { printf("%.3lf ",max(circle_S(r1),circle_S(r2))); continue; } else { double ans=circle_S(r1)+circle_S(r2); double j1=acos((r1*r1+dis*dis-r2*r2)/(2*r1*dis)); double l1=j1*2*r1; double j2=acos((r2*r2+dis*dis-r1*r1)/(2*r2*dis)); double l2=j2*2*r2; double s1=l1*r1*0.5; double s2=l2*r2*0.5; double s=r1*dis*sin(j1); ans-=(s1+s2-s); printf("%.3lf ",ans); } } }
约瑟夫环问题
公式推导：http://blog.csdn.net/u011500062/article/details/72855826?locationNum=6&fps=1
#include<cstdio> using namespace std; int main() { freopen("resist.in","r",stdin); freopen("resist.out","w",stdout); int n,k,ans=0; scanf("%d%d",&n,&k); for(int i=2;i<=n;i++) ans=(ans+k)%i; printf("%d",ans+1); }
贪心
最大值：
什么视图要求为x，就把对应的位置全弄成x
所以最后每个位置的高度为min（left[j],front[i]）
最小值：
先看主视图
如果主视图i=左视图j，且之前第j列没有高度能满足左视图j，那么（i，j）的高度就是主视图i
否则，任选一个左视图j>=主视图i的j，（i，j）的高度为主视图i
再看左视图
j已经被满足，忽略
否则，任选一个主视图i<=左视图j的i，（i，j）的高度为左视图j
#include<cstdio> #include<iostream> #define N 1011 using namespace std; int n,m; int front[N],leftt[N]; int maxn[N][N],minn[N][N]; int sumd,sumx; bool have[N]; void read(int &x) { x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar();} } int main() { freopen("neighbor.in","r",stdin); freopen("neighbor.out","w",stdout); read(n); read(m); for(int i=1;i<=n;i++) read(front[i]); for(int i=m;i;i--) read(leftt[i]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) maxn[i][j]=front[i]; for(int j=1;j<=m;j++) for(int i=1;i<=n;i++) maxn[i][j]=min(maxn[i][j],leftt[j]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sumd+=maxn[i][j]; bool ok; for(int i=1;i<=n;i++) { ok=false; for(int j=1;j<=m;j++) { if(have[j]) continue; if(leftt[j]==front[i]) { minn[i][j]=front[i]; have[j]=ok=true; break; } } if(ok) continue; for(int j=1;j<=m;j++) if(leftt[j]>=front[i]) { minn[i][j]=front[i]; break; } } for(int j=1;j<=m;j++) { ok=false; for(int i=1;i<=n;i++) if(minn[i][j]==leftt[j]) { ok=true; break; } if(ok) continue; for(int i=1;i<=n;i++) if(minn[i-1][j]==leftt[j]) { minn[i-1][j]=0; minn[i][j]=leftt[j]; ok=true; break; } if(ok) continue; for(int i=1;i<=n;i++) if(leftt[j]<=front[i]) { minn[i][j]=leftt[j]; break; } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sumx+=minn[i][j]; printf("%d %d",sumx,sumd); }