-
bzoj1074【Scoi2007】折纸
- 思路：考虑倒着做，每次将在折叠的直线右边的扔掉，左边的点再对称一次加入；
- 算几知识：求向量关于法向量的对称向量
- 点$A$关于点$B$对称的点$C = 2B - A$
- 如果要求$\vec{A}$关于法向量$\vec{l}$的对称向量$\vec{A'}$；
- 可以考虑都平移到原点
- 利用点积求出$\vec{A}$在$\vec{l}$上的投影点$D$， 再将点$A$关于$D$对称到$A'$；
- $A'$的坐标就是向量$\vec{A'}$
-
bzoj1074
1 #include<bits/stdc++.h> 2 #define db double 3 #define eps 1e-6 4 using namespace std; 5 const int N=1<<9; 6 int n,m,cnt,tmp; 7 int dcmp(db x){return fabs(x)<=eps?0:x<0?-1:1;} 8 struct point{ 9 db x,y; 10 point(db _x=0,db _y=0):x(_x),y(_y){}; 11 point operator +(const point&A)const{return point(x+A.x,y+A.y);} 12 point operator -(const point&A)const{return point(x-A.x,y-A.y);} 13 point operator *(const db&a)const{return point(x*a,y*a);} 14 db operator *(const point&A)const{return x*A.x+y*A.y;} 15 db operator ^(const point&A)const{return x*A.y-y*A.x;} 16 }p1[N],p2[N],q[N],qq[N]; 17 bool onleft(point A,point B,point C){ 18 return dcmp((C-B)^(A-B))>0; 19 } 20 point rev(point A,point B,point C){ 21 point D = C - B; 22 db l2 = D*D; 23 D = B + D*((A-B)*D/l2); 24 return D*2 - A; 25 } 26 int main(){ 27 #ifndef ONLINE_JUDGE 28 freopen("bzoj1074.in","r",stdin); 29 freopen("bzoj1074.out","w",stdout); 30 #endif 31 scanf("%d", &n); 32 for(int i=1;i<=n;i++)scanf("%lf%lf%lf%lf", &p1[i].x, &p1[i].y, &p2[i].x, &p2[i].y); 33 scanf("%d", &m); 34 for(int i=1;i<=m;i++){ 35 cnt=1;scanf("%lf%lf", &q[1].x, &q[1].y); 36 for(int j=n;j;j--){ 37 tmp=0; 38 for(int k=1;k<=cnt;k++)if(onleft(q[k],p1[j],p2[j])){ 39 qq[++tmp] = q[k]; 40 qq[++tmp] = rev(q[k],p1[j],p2[j]); 41 } 42 cnt=tmp; 43 if(!cnt)break; 44 for(int k=1;k<=cnt;k++)q[k]=qq[k]; 45 } 46 int ans=0; 47 // puts(""); 48 for(int j=1;j<=cnt;j++){ 49 // printf("%.2f %.2lf\n",q[j].x, q[j].y); 50 if(dcmp(q[j].x)>0&&dcmp(q[j].y)>0&&dcmp(100-q[j].x)>0&&dcmp(100-q[j].y)>0){ 51 ans ++; 52 } 53 } 54 printf("%d\n",ans); 55 } 56 return 0; 57 }
-
bzoj1094【Zjoi207】粒子运动
- 思路：每个例子的路径是$k$段折线，枚举每对粒子和时间段计算最近距离；
- 算几知识：
- 1.求变化有的轨迹直接求出和圆的交点做出法向量求对称，对称的方法同上；
- 2.求圆和向量的交点（保证有交）：
- 假设向量的起点$A$,方向$\vec{B}$，圆C的圆心为$O$，半径为$R$
- 所以$( (A-O) + t \vec{B} )^2 = R^2$
- 展开点积为常数，解二次方程即可；
-
bzoj1094
1 #include<bits/stdc++.h> 2 #define db double 3 #define il inline 4 using namespace std; 5 const int N=110; 6 int n,k; 7 db R,t[N][N]; 8 struct point{ 9 db x,y; 10 point(db _x=0,db _y=0):x(_x),y(_y){}; 11 point operator +(const point&A)const{return point(x+A.x,y+A.y);} 12 point operator -(const point&A)const{return point(x-A.x,y-A.y);} 13 point operator *(const db&a)const{return point(x*a,y*a);} 14 db operator *(const point&A)const{return x*A.x+y*A.y;} 15 db operator ^(const point&A)const{return x*A.y-y*A.x;} 16 }O,p[N][N],v[N][N]; 17 il db cal(db a,db b,db c){return ( -b + sqrt(b*b-4*a*c) ) / a / 2; } 18 il db len(point A){return sqrt(A*A);} 19 il db solve(int i,int j,int k1,int k2,db tl,db tr){ 20 point v1 = v[i][k1], v2 = v[j][k2]; 21 point p1 = p[i][k1] + v1 * (tl - t[i][k1]); 22 point p2 = p[j][k2] + v2 * (tl - t[j][k2]); 23 point tv = v1-v2, tp = p1-p2; tr-=tl; 24 db a=tv*tv,b=tv*tp*2,d=-b/a/2; 25 if(fabs(a)<1e-9)return b > 0 ? len(tv*tr+tp) : len(tv*tl+tp); 26 else { 27 d = max(0.0, min(tr, d)); 28 return len(tv*d+tp); 29 } 30 } 31 int main(){ 32 #ifndef ONLINE_JUDGE 33 freopen("bzoj1094.in", "r", stdin); 34 freopen("bzoj1094.out","w",stdout); 35 #endif 36 scanf("%lf%lf%lf",&O.x,&O.y,&R); 37 scanf("%d%d",&n,&k); 38 for(int i=1;i<=n;i++){ 39 scanf("%lf%lf%lf%lf",&p[i][0].x,&p[i][0].y,&v[i][0].x,&v[i][0].y); 40 for(int j=1;j<=k+1;j++){ 41 point tp = p[i][j-1] - O, tv = v[i][j-1]; 42 db tx = cal(tv*tv, tp*tv*2, tp*tp-R*R); 43 t[i][j] = t[i][j-1] + tx; 44 p[i][j] = p[i][j-1] + tv*tx; 45 point l = O - p[i][j]; swap(l.x,l.y),l.x=-l.x; 46 v[i][j] = l * ((tv*l)/(l*l)) * 2 - tv; 47 } 48 } 49 db ans = 1e18; 50 for(int i=1;i<=n;i++) 51 for(int j=1;j<=n;j++)if(i!=j){ 52 int k1=0,k2=0; 53 while(k1<=k&&k2<=k){ 54 ans = min(ans, solve(i, j, k1, k2, max(t[i][k1],t[j][k2]), min(t[i][k1+1],t[j][k2+1]))); 55 if(t[i][k1+1]<t[j][k2+1])k1++;else k2++; 56 } 57 } 58 printf("%.3lf\n",ans); 59 return 0; 60 }
- bzoj1043【Hnoi2008】下落的圆盘
- 思路：枚举每个圆盘后面落下的圆盘，求相交的弧度区域，分别对每个圆求弧度并之后统计没有被覆盖的部分；
- 算几知识：
- 1.极角：
- 利用$atan2(y,x)$可以求得一个点的极角(弧度)；
- 极角范围$(-\pi,\pi]$，大小逆时针(-x轴，-x轴]不断增大；
- x轴上半部分$+x$轴到$-x$轴不断增大，下半$-x$轴到$+x$轴不断增大；
- 特别注意的是：$+x$轴为$0$，$-x$为$\pi$，$x$轴上方为正，下方为负，；
- 如果一个区间跨越了-x轴，那么需要分成两个区间处理；
- 2.求两圆交点及相交的极角弧度范围：
- 设小圆$O_{1}$半径$r_{1}$，大圆$O_{2}$半径$r_{2}$，圆心距$|O1O2| = d$，两个交点分别为$P_{1}$,$P_{2}$;
- 首先判断位置关系：$d > r_{1} + r_{2}$相离，$d < r_{2} - r_{1}$包含，都没有交点;
- （不考虑相切）然后：
- 在$\triangle O1O2P1$中用余弦定理算出$ \angle P_{1}O_{1}O_{2}$，利用$\vec{O_{1}O_{2}}$上下旋转调整可得$\vec{O_{1}P_{1}} , \vec{O_{1}P_{2}}$ ，由此可以算出$P_{1}P_{2}$
-
bzoj1043
1 #include<bits/stdc++.h> 2 #define db double 3 #define eps 1e-9 4 using namespace std; 5 const int N=1010; 6 const db pi = acos(-1); 7 int n,tot1[N],tot2[N],vis[N]; 8 db sub2[N][N<<2],cnt[N<<2]; 9 struct point{ 10 db x,y; 11 point(db _x=0,db _y=0):x(_x),y(_y){}; 12 point operator +(const point&A)const{return point(x+A.x,y+A.y);} 13 point operator -(const point&A)const{return point(x-A.x,y-A.y);} 14 db operator *(const point&A)const{return x*A.x+y*A.y;} 15 db operator ^(const point&A)const{return x*A.y-y*A.x;} 16 point operator *(const db&a)const{return point(x*a,y*a);} 17 }sub1[N][N<<2]; 18 struct circle{point o;db r;}c[N]; 19 int dcmp(db x){return fabs(x)<eps?0:x<0?-1:1;} 20 db len(point A){return sqrt(A*A);} 21 point rotate(point A,db cos,db sin){return point(A.x*cos-A.y*sin, A.y*cos+A.x*sin);} 22 void ins(int i,point p1,point p2){ 23 db l = atan2(p1.y,p1.x), r = atan2(p2.y,p2.x); 24 sub2[i][++tot2[i]] = l; 25 sub2[i][++tot2[i]] = r; 26 if(dcmp(l-r)>0){ 27 sub1[i][++tot1[i]]=point(-pi,r); 28 sub1[i][++tot1[i]]=point(l,pi); 29 }else sub1[i][++tot1[i]]=point(l,r); 30 } 31 void solve(int i,int j){ 32 if(dcmp(c[i].r-c[j].r)>0)swap(i,j); 33 point td = c[j].o - c[i].o,p0,p1,p2; 34 db d = len(td), r1=c[i].r, r2=c[j].r; 35 if(dcmp(d-r1-r2)>=0)return ; 36 if(dcmp(d-r2+r1)<=0){if(i<j)vis[i]=1;return ;} 37 db Cos = (td*td + r1*r1 - r2*r2) /d /r1 /2 ; 38 db Sin = sqrt(1-Cos*Cos); 39 p0 = td * (r1/d); 40 p1 = c[i].o + rotate(p0,Cos,-Sin);// 41 p2 = c[i].o + rotate(p0,Cos,Sin); 42 if(i<j)ins(i,p1-c[i].o, p2-c[i].o); 43 else ins(j,p2-c[j].o, p1-c[j].o); 44 } 45 int main(){ 46 freopen("bzoj1043.in","r",stdin); 47 freopen("bzoj1043.out","w",stdout); 48 scanf("%d",&n); 49 for(int i=1;i<=n;i++){ 50 scanf("%lf%lf%lf",&c[i].r,&c[i].o.x,&c[i].o.y); 51 for(int j=i-1;j;j--)solve(j,i); 52 } 53 db ans = 0; 54 for(int i=1;i<=n;i++){ 55 if(vis[i])continue; 56 sub2[i][++tot2[i]]=-pi; 57 sub2[i][++tot2[i]]=pi; 58 sort(sub2[i]+1,sub2[i]+tot2[i]+1); 59 for(int j=1;j<=tot2[i];j++)cnt[j]=0; 60 for(int j=1;j<=tot1[i];j++){ 61 int p1 = lower_bound(sub2[i]+1,sub2[i]+tot2[i]+1,sub1[i][j].x) - sub2[i]; 62 int p2 = lower_bound(sub2[i]+1,sub2[i]+tot2[i]+1,sub1[i][j].y) - sub2[i]; 63 cnt[p1]--,cnt[p2]++; 64 } 65 db all = 0; 66 for(int j=1;j<tot2[i];j++){ 67 cnt[j]+=cnt[j-1]; 68 if(!cnt[j])all += sub2[i][j+1]-sub2[i][j]; 69 } 70 ans += all * c[i].r; 71 } 72 printf("%.3lf\n", ans); 73 }
- bzoj2433【Noi2011】智能车比赛
- 思路：处理相邻两个矩形的y坐标并$[l,r]$，可以通过的是这段，由于只会向右移动，所以利用斜率判断是否可走，直接dp即可；
- 也没有什么知识，注意使用到了斜率的话一定要注意在x坐标相同的特判，这题主要是s和t点的位置：
- 所以在同一x坐标上的[l,r]意义可能不同，特判s，t的位置再调整一下dp边界；
-
bzoj2433
1 #include<bits/stdc++.h> 2 #define inf 1e18 3 #define db double 4 #define eps 1e-8 5 using namespace std; 6 const int N=2010; 7 int n; 8 db f[N][2],pv,qx[N],qy1[N],qy2[N]; 9 int dcmp(db x){return fabs(x)<eps?0:x<0?-1:1;} 10 struct point{ 11 db x,y; 12 point(db _x=0,db _y=0):x(_x),y(_y){}; 13 }s,t,p[N][2]; 14 db calk(point x,point y){ 15 if(!dcmp(x.x-y.x))return dcmp(x.y-y.y)*inf; 16 return (y.y-x.y)/(y.x-x.x); 17 } 18 db dis(point x,point y){return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));} 19 void relax(point&tp,int&pos,int typ){ 20 if(tp.x==qx[pos]){ 21 if(tp.y==p[pos][0].y)tp.y+=eps; 22 if(tp.y==p[pos][1].y)tp.y-=eps; 23 int tmp = typ>0?pos:pos-1; 24 if(dcmp(tp.y-qy1[tmp])>=0&&dcmp(tp.y-qy2[tmp])<=0)pos+=typ; 25 } 26 } 27 int main(){ 28 #ifndef ONLINE_JUDGE 29 //freopen("bzoj2433.in","r",stdin); 30 //freopen("bzoj2433.out","w",stdout); 31 #endif 32 scanf("%d",&n); 33 for(int i=1;i<=n;i++)scanf("%lf%lf%lf%lf",&qx[i],&qy1[i],&qx[i+1],&qy2[i]); 34 scanf("%lf%lf%lf%lf%lf",&s.x,&s.y,&t.x,&t.y,&pv); 35 if(s.x>t.x)swap(s,t); 36 qy1[0]=-inf,qy2[0]=inf; 37 for(int i=1;i<=n;i++){ 38 p[i][0] = point(qx[i],max(qy1[i],qy1[i-1])); 39 p[i][1] = point(qx[i],min(qy2[i],qy2[i-1])); 40 for(int j=0;j<2;j++)f[i][j]=inf; 41 } 42 int ps = lower_bound(qx+1,qx+n+1,s.x-eps)-qx; 43 int pt = lower_bound(qx+1,qx+n+1,t.x+eps)-qx-1; 44 db l,r,t1,t2; 45 relax(s,ps,1); 46 relax(t,pt,-1); 47 for(int i=ps;i<=pt;i++) 48 for(int j=0;j<2;j++){ 49 l=-inf,r=inf; 50 point now = p[i][j]; 51 for(int k=i-1;k>=ps;k--){ 52 l = max(l, t1=calk(now,p[k][1])); 53 r = min(r, t2=calk(now,p[k][0])); 54 if(dcmp(t2-l)>=0&&dcmp(t2-r)<=0){ 55 f[i][j] = min(f[i][j], f[k][0] + dis(now,p[k][0])); 56 } 57 if(dcmp(t1-l)>=0&&dcmp(t1-r)<=0){ 58 f[i][j] = min(f[i][j], f[k][1] + dis(now,p[k][1])); 59 } 60 } 61 t1=calk(s,now); 62 if(dcmp(t1-l)>=0&&dcmp(t1-r)<=0)f[i][j]=min(f[i][j],dis(s,now)); 63 } 64 db ans=inf; 65 l=-inf;r=inf; 66 for(int i=pt;i>=ps;i--){ 67 l=max(l,t1=calk(t,p[i][1])); 68 r=min(r,t2=calk(t,p[i][0])); 69 if(dcmp(t2-l)>=0&&dcmp(t2-r)<=0){ 70 ans = min(ans, f[i][0]+dis(p[i][0],t)); 71 } 72 if(dcmp(t1-l)>=0&&dcmp(t1-r)<=0){ 73 ans = min(ans, f[i][1]+dis(p[i][1],t)); 74 } 75 } 76 t1=calk(s,t); 77 if(dcmp(t1-l)>=0&&dcmp(t1-r)<=0){ 78 ans = min(ans,dis(s,t)); 79 } 80 ans /= pv; 81 printf("%.8lf\n",ans); 82 return 0; 83 }
