题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1014
作者：everlasting
模板：NTT
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
#include<bits/stdc++.h> #define maxn 60060*3 #define ll long long #define mod 998244353 #define g 3 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } int n,m; int rev[maxn],c[maxn]; int a[maxn],b[maxn]; inline void init(){ n=rd(); static char ch[maxn]; scanf("%s",ch); for(int i=0; i<n; i++)a[i]=ch[n-i-1]-'0'; scanf("%s",ch); for(int i=0; i<n; i++)b[i]=ch[n-i-1]-'0'; } inline int ksm(int A,int B){ int ret=1; while(B){ if(B%2)ret=(ll)A*ret%mod; A=(ll)A*A%mod; B/=2; } return ret; } void ntt(int *A,int flag){ int bit=0; while((1<<bit)<n)bit++; for(int i=0; i<n; i++){ rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1)); if(i<rev[i])swap(A[i],A[rev[i]]); } for(int len=1; len<n; len*=2){ int tmp=ksm(g,(mod-1)/(len*2)); if(flag==-1)tmp=ksm(tmp,mod-2); for(int i=0; i<n; i+=len*2){ int w=1; for(int j=0; j<len; j++,w=(ll)w*tmp%mod){ int x=A[i+j]; int y=(ll)w*A[i+j+len]%mod; A[i+j]=(x+y)%mod; A[i+j+len]=(x-y+mod)%mod; } } } int inv=ksm(n,mod-2); if(flag==-1)for(int i=0; i<n; i++)A[i]=(ll)A[i]*inv%mod; } inline void work(){ m=n*2; for(n=1; n<m; n*=2); ntt(a,1); ntt(b,1); for(int i=0; i<n; i++)a[i]=(ll)a[i]*b[i]%mod; ntt(a,-1); for(int i=0; i<m; i++)c[i]=a[i]; while(c[m-1]==0)m--; for(int i=0; i<m; i++){ if(c[i]>=10){ c[i+1]+=c[i]/10; c[i]%=10; if(i==m-1)m++; } } for(int i=m-1; i>=0; i--)printf("%d",c[i]); puts(""); } int main(){ init(); work(); return 0; } |
模板：FFT
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include<bits/stdc++.h> #define db double #define maxn 60060*3 #define cp complex<db> #define pi acos(-1) using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } int n,m; int rev[maxn],c[maxn]; cp a[maxn],b[maxn]; inline void init(){ n=rd(); static char ch[maxn]; scanf("%s",ch); for(int i=0; i<n; i++)a[i]=ch[n-i-1]-'0'; scanf("%s",ch); for(int i=0; i<n; i++)b[i]=ch[n-i-1]-'0'; } void fft(cp *A,int flag){ int bit=0; while((1<<bit)<n)bit++; for(int i=0; i<n; i++){ rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1)); if(i<rev[i])swap(A[i],A[rev[i]]); } for(int len=1; len<n; len*=2){ cp tmp(cos(pi/len),flag*sin(pi/len)); for(int i=0; i<n; i+=len*2){ cp w(1,0); for(int j=0; j<len; j++,w*=tmp){ cp x=A[i+j]; cp y=w*A[i+j+len]; A[i+j]=x+y; A[i+j+len]=x-y; } } } if(flag==-1)for(int i=0; i<n; i++)A[i]/=n; } inline void work(){ m=n*2; for(n=1; n<m; n*=2); fft(a,1); fft(b,1); for(int i=0; i<n; i++)a[i]*=b[i]; fft(a,-1); for(int i=0; i<m; i++)c[i]=(int)(a[i].real()+0.5); while(c[m-1]==0)m--; for(int i=0; i<m; i++){ if(c[i]>=10){ c[i+1]+=c[i]/10; c[i]%=10; if(i==m-1)m++; } } for(int i=m-1; i>=0; i--)printf("%d",c[i]); puts(""); } int main(){ init(); work(); return 0; } |
模板：半平面交
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#include<bits/stdc++.h> #define db double #define maxn 505 #define eps 1e-7 #define Vector point using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct point{ db x,y; point(db xx=0,db yy=0){x=xx,y=yy;} friend point operator + (Vector a,Vector b){return point(a.x+b.x,a.y+b.y);} friend point operator - (Vector a,Vector b){return point(a.x-b.x,a.y-b.y);} friend point operator * (Vector a,db b){return point(a.x*b,a.y*b);} friend point operator / (Vector a,db b){return point(a.x/b,a.y/b);} friend bool operator < (Vector a,Vector b){return a.x<b.x || fabs(a.x-b.x)<eps && a.y<b.y;} }p[maxn],a[maxn]; struct line{ point p,v; db ang; line(){} line(point P,Vector V){ p=P; v=V; ang=atan2(v.y,v.x); } friend bool operator < (line a,line b){ return a.ang<b.ang; } }L[maxn],q[maxn]; inline db cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}//叉积 inline point GetPoint(line a,line b){//用叉积计算面积，用相似计算交点 Vector V=a.p-b.p; db t=cross(b.v,V)/cross(a.v,b.v); return a.p+a.v*t; } inline bool Onleft(line l,point p){//点是否在向量的左边 return cross(l.v,p-l.p)>0; } int cnt; inline void init(){ int T=rd(); while(T--){ int n=rd(); for(int i=1; i<=n; i++)p[i].x=rd(),p[i].y=rd(); p[n+1]=p[1]; for(int i=1; i<=n; i++)L[++cnt]=line(p[i],p[i+1]-p[i]);//把给定的多边形的所有边变成向量放进集合 } } int head=1,tail=0; inline void hpi(){ sort(L+1,L+cnt+1); q[++tail]=L[1]; for(int i=2; i<=cnt; i++){//把向量依次插入 while(head<tail && !Onleft(L[i],p[tail-1]))tail--;//如果队尾的交点在当前向量的右边，就删掉 while(head<tail && !Onleft(L[i],p[head]))head++;//对队头做相同的处理 q[++tail]=L[i];//把新的向量加进队列 if(fabs(cross(q[tail].v,q[tail-1].v))<eps){//如果新的向量和上一条边是平行的，需要删掉 tail--; if(Onleft(q[tail],L[i].p))q[tail]=L[i]; } if(head<tail)p[tail-1]=GetPoint(q[tail-1],q[tail]);//计算一下新的交点的坐标 } while(head<tail && !Onleft(q[head],p[tail-1]))tail--;//最后进行封口，假装插入一下head，把队尾不合法的向量删掉 p[tail]=GetPoint(q[tail],q[head]);//算一下最后的那个交点 } inline void work(){ hpi(); db ans=0; for(int i=head+1; i<tail; i++){ ans+=cross(p[i]-p[head],p[i+1]-p[head]);//计算面积 } printf("%.3lf\n",ans*0.5); } int main(){ init(); work(); return 0; } |
