A. Alice in the Wonderland

按題意模擬。

#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x, y) memset(x, y, sizeof(x)) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; } template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; } const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f; template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; } int casenum, casei;struct A {int x, y, z; }t, tt, st, ed; queue<A> q; int n, m, h; char s[60][60][60]; bool e[60][60][60]; const int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};int main() {scanf("%d%d%d", &n, &m, &h);for(int i = 1; i <= h; i ++){for(int j = 1; j <= n; j ++){scanf("%s", s[i][j] + 1);}}for(int i = 1; i <= h; i ++){for(int j = 1; j <= n; j ++){for(int k = 1; k <= m; k ++){if(s[i][j][k] == 'A'){st.x = j; st.y = k; st.z = i;}else if(s[i][j][k] == 'E'){ed.x = j; ed.y = k; ed.z = i;}}}}int flag = 0;q.push(st);e[st.z][st.x][st.y] = 1;while(! q.empty()){t = q.front(); q.pop();if(s[t.z][t.x][t.y] == 'E'){flag = 1;break;}if(s[t.z][t.x][t.y] == 'w'){int i;for(i = t.z; i <= h; i ++){ // 這里的方向要確認一下if(s[i][t.x][t.y] != 'w'){break;}} i --;if(e[i][t.x][t.y] == 0){tt.z = i; tt.x = t.x; tt.y = t.y;q.push(tt);e[i][t.x][t.y] = 1;}if(i != t.z) continue;}if(s[t.z][t.x][t.y] == 's'){for(int i = t.z; i <= h; i ++){if(s[i][t.x][t.y] == 's' && e[i][t.x][t.y] == 0){e[i][t.x][t.y] = 1;tt.z = i; tt.x = t.x; tt.y = t.y;q.push(tt);}else if(s[i][t.x][t.y] != 's') break;}for(int i = t.z; i >= 1; i --){if(s[i][t.x][t.y] == 's' && e[i][t.x][t.y] == 0){e[i][t.x][t.y] = 1;tt.z = i; tt.x = t.x; tt.y = t.y;q.push(tt);}else if(s[i][t.x][t.y] != 's') break;}}for(int i = 0; i < 4; i ++){tt.x = t.x + dx[i];tt.y = t.y + dy[i];tt.z = t.z;if(tt.x >= 1 && tt.x <= n && tt.y >= 1 && tt.y <= m && e[tt.z][tt.x][tt.y] == 0){q.push(tt);e[tt.z][tt.x][tt.y] = 1;}}}if(flag) puts("Yes"); else puts("No");return 0; } /* 【trick&&吐槽】【題意】【分析】3 3 3 A.. .w. ... ... .wE ... ... .w. ...【時間復雜度&&優化】 3 3 3 ... s.E ... ... s.. ... ... s.A ...*/

　　

B. Batrachomyomachia

貪心，每次選承受能力最小的可行的。

#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x, y) memset(x, y, sizeof(x)) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; } template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; } const int N = 210, M = 1e4 + 10, Z = 1e9 + 7, inf = 0x3f3f3f3f; template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; } int casenum, casei; int n, w; const double eps = 1e-12; int a[N][N], b[M]; double f[N][N]; bool del[111111]; multiset<int> sot; multiset<int> :: iterator it, ir; int sgn(double x){if(fabs(x) < eps) return 0;return x > 0 ? 1 : -1; } int main() {scanf("%d%d", &n, &w);for(int i = 1; i < n; i ++) scanf("%d", &b[i]);sort(b+1,b+n);for(int i = 1; i <= 200; i ++){for(int j = 1; j <= i; j ++){a[i][j] = w;}}for(int i = 1; i <= 200; i ++){for(int j = 1; j <= i; j ++){f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) / 2 + (a[i - 1][j] + a[i - 1][j - 1]) / 2;}}for(int i=1;i<=200;i++){sort(f[i] + 1, f[i] + i + 1);reverse(f[i] + 1, f[i] + i + 1);}/*for(int i = 1; i <= 10; i ++){for(int j = 1; j <= i; j ++){printf("%.0f ", f[i][j]);}puts("");}*/int ans = 0;for(int i = 2; i <= 200; i ++){for(int j = 1; j <= i; j ++){int flag=0;for(int k=1;k<n;k++)if(!del[k]&&sgn(b[k] - f[i][j])>=0){flag=k;break;}if(!flag){ans = i - 1;break;}del[flag]=1;}if(ans) break;}printf("%d\n", ans);return 0; } /* 【trick&&吐槽】【題意】【分析】【時間復雜度&&優化】*/

　　

C. Cherries

將所有數字排序，那么一定是選取連續$B-A+1$個數進行配對，枚舉所有方案即可。

#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x, y) memset(x, y, sizeof(x)) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; } template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; } const int N = 5050, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f; template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; } int casenum, casei; int n; int a[N]; int main() {while(~scanf("%d", &n)){int A, B;scanf("%d%d", &A, &B);for(int i = 1; i <= n; ++i){scanf("%d", &a[i]);}sort(a + 1, a + n + 1);int len = B - A;LL ans = 1e18;for(int i = 1; i + len <= n; ++i){int j = i + len;LL tmp = 0;for(int k = i, x = A; k <= j; ++k, ++x){tmp += abs(a[k] - x);}gmin(ans, tmp);}printf("%lld\n", ans);}return 0; } /* 【trick&&吐槽】【題意】【分析】【時間復雜度&&優化】*/

　　

D. Divisibility Game

預處理出約數集合后爆搜+卡時即可通過。

#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; const int N=401; const int lim=7; const int lim2=3; int i,j,x,now,ans,sum,ave,n,a[N],q[N]; vector<int>d[N]; int ED1 = CLOCKS_PER_SEC * 0.65; int ED2 = CLOCKS_PER_SEC * 0.95; void dfs(int s,int x){if(x>n){for(int i=1;i<=n;i++)printf("%d ",q[i]);exit(0);}if(clock() > ED1){return;//puts("-1");//exit(0);}for(vector<int>::iterator w=d[s].begin();w!=d[s].end();w++)for(int j=min(a[*w],1);j;j--){a[*w]-=j;for(int o=0;o<j;o++)q[x+o]=*w;dfs(s+(*w)*j,x+j);a[*w]+=j;} } void dfs2(int s,int x){if(x>n){for(int i=1;i<=n;i++)printf("%d ",q[i]);exit(0);}if(clock() > ED2){puts("-1");exit(0);}for(vector<int>::iterator w=d[s].begin();w!=d[s].end();w++)for(int j=min(a[*w],1);j;j--){a[*w]-=j;for(int o=0;o<j;o++)q[x+o]=*w;dfs2(s+(*w)*j,x+j);a[*w]+=j;} } int main(){scanf("%d",&n);for(i=0;i<n;i++)scanf("%d",&x),a[x]++,sum+=x;for(i=0;i<=sum;i++){for(j=lim+1;j<=13;j++)// for(j=13;j;j--)if(i%j==0&&a[j])d[i].push_back(j);for(j=lim2+1;j<=lim;j++)// for(j=13;j;j--)if(i%j==0&&a[j])d[i].push_back(j);for(j=lim2;j;j--)if(i%j==0&&a[j])d[i].push_back(j);}dfs(0,1);for(i=0;i<=sum;i++)reverse(d[i].begin(),d[i].end());dfs2(0,1);puts("-1"); }

　　

E. Enter the Word

設$dp[i]$表示打出前$i$個字符的最小代價，那么有$dp[i-1]\leq dp[i]\leq dp[i-1]+1$。

為了檢查是否可以不$+1$，找到$dp$值的分界線，那么只要后面部分是前面部分的子串即可。

設$f[i]$表示子串匹配結束位置是$i$是否可行，可以通過bitset加速。

時間復雜度$O(\frac{n^2}{64})$。

#include<cstdio> #include<bitset> #include<cstring> using namespace std; const int N=200010; int n,i,r,ans;char a[N];bitset<N>f,v[26]; int main(){scanf("%s",a);n=strlen(a);for(i=0;i<n;i++){a[i]-='a';f=f<<1&v[a[i]];if(!f.any()){for(int k=r;k<i;k++)v[a[k]][k]=1;r=i;ans++;f=v[a[i]];}}printf("%d",ans); }

　　

F. Formula 1

按題意模擬即可，記錄每個人的排名以及領先的圈數。

#include<cstdio> #include<algorithm> using namespace std; const int N=100010; int n,m,i,x,f[N],pos[N],g[N]; bool cmp(int x,int y){return g[x]==g[y]?pos[x]<pos[y]:g[x]>g[y];} int main(){scanf("%d%d",&n,&m);for(i=1;i<=n;i++){f[i]=i;pos[i]=i;}while(m--){scanf("%d",&x);for(i=1;i<=n;i++)if(f[i]==x)break;int o=i;if(o==1){g[x]++;for(i=1;i<n;i++)f[i]=f[i+1];f[n]=x;swap(f[n],f[n-1]);}else swap(f[o],f[o-1]);//for(i=1;i<=n;i++)printf("%d ",f[i]);puts("");}for(i=1;i<=n;i++)pos[f[i]]=i;sort(f+1,f+n+1,cmp);for(i=1;i<=n&&i<=6;i++)printf("%d ",f[i]); }

　　

G. Game with Coins

將過程倒過來，則變成對于最后一個數，找到倒數第二個數，然后中間的數都要被最后一個數覆蓋掉，區間DP即可。

#include<cstdio> #include<algorithm> using namespace std; const int N=110; int n,i,j,a[N],f[N][N],ans; int dfs(int l,int r){if(~f[l][r])return f[l][r];int&t=f[l][r];t=0;int left=l+1,right=r;if(left>right)right+=n;for(int i=left;i<=right;i++)t=max(t,dfs(l,(i-1+n)%n)+dfs(i%n,r)+abs(a[l]-a[i%n]));return t; } int main(){scanf("%d",&n);for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<n;i++)for(j=0;j<n;j++)if(i!=j)f[i][j]=-1;for(i=0;i<n;i++)for(j=0;j<n;j++)ans=max(ans,dfs(i,j));printf("%d",ans); }

　　

H. Hamnattan

首先特判起點終點都在同一條街道上的情況。其余情況Dijkstra求最短路即可，需要現算代價。

#include<cstdio> #include<queue> #include<cstdlib> #include<algorithm> #include<vector> using namespace std; typedef long long ll; typedef pair<int,int>P; typedef pair<ll,P>PI; typedef pair<ll,PI>PII; const ll inf=1LL<<60; const int N=110,M=500000; int sa[N],sb[N]; int n,m,i,j,x,y,a[N],b[N],ns[N][N],ew[N][N],s[N][N]; int sx,sy,ex,ey; ll d[N][N]; int g[N][N],v[M][2],w[M][2],nxt[M],ed; priority_queue<PI,vector<PI>,greater<PI> >q; ll ans=inf; inline void add(int x,int y,int xx,int yy,int z,int zz){v[++ed][0]=xx;v[ed][1]=yy;w[ed][0]=z;w[ed][1]=zz;nxt[ed]=g[x][y];g[x][y]=ed; } inline void add2(int x,int y,int xx,int yy,int w,int ww){add(x,y,xx,yy,w,ww);add(xx,yy,x,y,w,ww); } inline int col(int x,int y,ll z){int NS=ns[x][y],EW=ew[x][y],S=s[x][y];z%=NS+EW;if(S)return z<EW;return z>=NS; } inline ll cal(int x,int y,int dir,ll z){while(col(x,y,z)!=dir)z++;return z; } inline void ext(int x,int y,ll z){if(d[x][y]>z)q.push(PI(d[x][y]=z,P(x,y))); } void CHECK(){int i,j;for(i=1;i<=n;i++)for(j=1;j<=m;j++){if(sy==ey)if(i<n)if(sb[j-1]==sy)if(sa[i-1]<=sx&&sx<=sa[i])if(sa[i-1]<=ex&&ex<=sa[i]){printf("%d",abs(sx-ex)+abs(sy-ey));exit(0);}if(sx==ex)if(j<m)if(sa[i-1]==sx)if(sb[j-1]<=sy&&sy<=sb[j])if(sb[j-1]<=ey&&ey<=sb[j]){printf("%d",abs(sx-ex)+abs(sy-ey));exit(0);}} } void EXT(int x,int y){int i,j;for(i=1;i<=n;i++)for(j=1;j<=m;j++){if(i<n)if(sb[j-1]==y)if(sa[i-1]<=x&&x<=sa[i]){ext(i,j,cal(i,j,1,x-sa[i-1]));ext(i+1,j,cal(i+1,j,1,sa[i]-x));}if(j<m)if(sa[i-1]==x)if(sb[j-1]<=y&&y<=sb[j]){ext(i,j,cal(i,j,0,y-sb[j-1]));ext(i,j+1,cal(i,j+1,0,sb[j]-y));}} } void FIN(int x,int y){int i,j;for(i=1;i<=n;i++)for(j=1;j<=m;j++){if(i<n)if(sb[j-1]==y)if(sa[i-1]<=x&&x<=sa[i]){ans=min(ans,d[i][j]+x-sa[i-1]);ans=min(ans,d[i+1][j]+sa[i]-x);}if(j<m)if(sa[i-1]==x)if(sb[j-1]<=y&&y<=sb[j]){ans=min(ans,d[i][j]+y-sb[j-1]);ans=min(ans,d[i][j+1]+sb[j]-y);}} } int main(){scanf("%d%d",&n,&m);for(i=1;i<n;i++){scanf("%d",&a[i]);sa[i]=sa[i-1]+a[i];}for(i=1;i<m;i++){scanf("%d",&b[i]);sb[i]=sb[i-1]+b[i];}for(i=1;i<=n;i++)for(j=1;j<=m;j++){if(i<n)add2(i,j,i+1,j,a[i],1);if(j<m)add2(i,j,i,j+1,b[j],0);}for(j=1;j<=m;j++)for(i=1;i<=n;i++)scanf("%d%d%d",&ns[i][j],&ew[i][j],&s[i][j]);scanf("%d%d%d%d",&sx,&sy,&ex,&ey);CHECK();for(i=1;i<=n;i++)for(j=1;j<=m;j++)d[i][j]=inf;EXT(sx,sy);while(!q.empty()){PI t=q.top();q.pop();int x=t.second.first,y=t.second.second;if(d[x][y]<t.first)continue;//printf("%d %d %lld\n",x,y,t.first);for(i=g[x][y];i;i=nxt[i]){ext(v[i][0],v[i][1],cal(v[i][0],v[i][1],w[i][1],t.first+w[i][0]));}}FIN(ex,ey);printf("%lld",ans); } /* 4 3 10 10 10 10 10 1 99 0 99 1 0 50 99 0 1 99 1 1 99 0 99 1 0 20 41 1 1 99 0 99 1 0 1 99 1 99 1 0 99 1 0 1 10 30 19 */

　　

I. Integer Pairs

只要$a[j]<0$即合法。

#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x, y) memset(x, y, sizeof(x)) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; } template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; } const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f; template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; } int casenum, casei; int n; int main() {while(~scanf("%d", &n)){int neg = 0;for(int i = 1; i <= n; ++i){int x; scanf("%d", &x);neg += x < 0;}LL ans = neg * (n - 1ll);printf("%lld\n", ans);}return 0; } /* 【trick&&吐槽】【題意】【分析】【時間復雜度&&優化】 3 -1 -2 -3*/

　　

J. Jedi Training

線段樹維護$f[l][r]$表示對應區間內選擇子序列的左端點奇偶性為$l$，右端點奇偶性為$r$時的最大和。

#include<cstdio> #include<algorithm> using namespace std; #define rep(i) for(int i=0;i<2;i++) typedef long long ll; const int N=100010,M=262150; const ll inf=1LL<<60; int n,m,i,a[N],op,x,y; inline void up(ll&a,ll b){a<b?(a=b):0;} struct E{ll f[2][2];E(){rep(i)rep(j)f[i][j]=-inf;}void clr(){rep(i)rep(j)f[i][j]=-inf;}void set(int x,ll p){clr();f[x&1][x&1]=p;}E operator+(const E&b){E c;rep(i)rep(j)c.f[i][j]=max(f[i][j],b.f[i][j]);rep(i)rep(j)rep(k)up(c.f[i][k],f[i][j]+b.f[j^1][k]);return c;}void write(){ll t=-inf;rep(i)rep(j)up(t,f[i][j]);printf("%lld\n",t);} }v[M]; void build(int x,int a,int b){if(a==b){v[x].set(a,::a[a]);return;}int mid=(a+b)>>1;build(x<<1,a,mid),build(x<<1|1,mid+1,b);v[x]=v[x<<1]+v[x<<1|1]; } void change(int x,int a,int b,int c,int d){if(a==b){v[x].set(a,d);return;}int mid=(a+b)>>1;if(c<=mid)change(x<<1,a,mid,c,d);else change(x<<1|1,mid+1,b,c,d);v[x]=v[x<<1]+v[x<<1|1]; } E ask(int x,int a,int b,int c,int d){if(c<=a&&b<=d)return v[x];int mid=(a+b)>>1;E t;t.clr();if(c<=mid)t=ask(x<<1,a,mid,c,d);if(d>mid)t=t+ask(x<<1|1,mid+1,b,c,d);return t; } int main(){scanf("%d%d",&n,&m);for(i=1;i<=n;i++)scanf("%d",&a[i]);build(1,1,n);while(m--){scanf("%d%d%d",&op,&x,&y);if(op==1)change(1,1,n,x,y);else{ask(1,1,n,x,y).write();}} }

　　

K. Kings of a Round Table

假設$1$號國王一定位于$1$號位置，并不區分剩下$7$個國王，則這種情況下方案數還要乘以$n\times 7!$。

那么剩下的方案數大約只有$3\times 10^8$個，爆搜打表即可。

#include<cstdio> long long f[111]; int n; int main(){f[9]=0;f[10]=0;f[11]=0;f[12]=0;f[13]=0;f[14]=0;f[15]=0;f[16]=0;f[17]=685440;f[18]=725760;f[19]=11491200;f[20]=6451200;f[21]=83825280;f[22]=38142720;f[23]=397837440;f[24]=170311680;f[25]=1441440000;f[26]=617460480;f[27]=4330609920;f[28]=1905684480;f[29]=11330323200;f[30]=5175878400;f[31]=26645794560;f[32]=12675317760;f[33]=57564017280;f[34]=28504707840;f[35]=116035920000;f[36]=59698114560;f[37]=220799779200;f[38]=117723513600;f[39]=400156848000;f[40]=220502016000;f[41]=695520483840;f[42]=395054150400;f[43]=1165870379520;f[44]=680891904000;f[45]=1893253824000;f[46]=1134285546240;f[47]=2989486241280;f[48]=1833544581120;f[49]=4604213577600;f[50]=2885462496000;f[51]=6934509429120;f[52]=4433085296640;f[53]=10236190124160;f[54]=6664974140160;f[55]=14837041296000;f[56]=9826142699520;f[57]=21152159804160;f[58]=14230860215040;f[59]=29701625184000;f[60]=20277521510400;f[61]=41130725126400;f[62]=28465795572480;f[63]=56232969811200;f[64]=39416274616320;f[65]=75976140240000;f[66]=53892855878400;f[67]=101531626035840;f[68]=72828098703360;f[69]=134307318499200;f[70]=97351809811200;scanf("%d",&n);printf("%lld",f[n]); }

　　

L. Lines and Polygon

求出直線與凸包的交點，然后在附近枚舉即可得到最近點。

#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x, y) memset(x, y, sizeof(x)) #define ls o<<1 #define rs o<<1|1 typedef unsigned long long UL; typedef unsigned int UI; template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; } template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; } const int N = 1e5 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f; template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; } int casenum, casei;const long double eps = 1e-8; int sgn(double x) {if(fabs(x) < eps) return 0;return x > 0 ? 1 : -1; } struct point {long double x, y;point(){}point(long double a, long double b){x = a; y = b;}long double det (const point &b)const{return x * b.y - y * b.x;}friend bool operator < (const point &a, const point &b){if(sgn(a.x - b.x) == 0) return sgn(a.y - b.y) < 0;return sgn(a.x - b.x) < 0;}friend point operator - (const point &a, const point &b){return point(a.x - b.x, a.y - b.y);} }; struct Convex {int n;vector<point> a, upper, lower;Convex(){}Convex (vector<point> _a) : a(_a){n = a.size();int ptr = 0;for(int i = 1; i < n; i ++) if(a[ptr] < a[i]) ptr = i;for(int i = 0; i <= ptr; i ++) lower.push_back(a[i]);for(int i = ptr; i < n; i ++) upper.push_back(a[i]);upper.push_back(a[0]);}int sign(long double x){if(fabs(x) < eps) return 0;return x > 0 ? 1 : -1;}pair<long double, int> get_tangent(vector<point> &convex, point vec){int l = 0, r = (int) convex.size() - 2;for(; l + 1 < r;){int mid = (l + r) / 2;if(sign((convex[mid + 1] - convex[mid]).det(vec)) > 0) r = mid;else l = mid;}return max(make_pair(vec.det(convex[r]), r), make_pair(vec.det(convex[0]), 0));}int binary_search(point u, point v, int l, int r){int sl = sign((v - u).det(a[l % n] - u));for(; l + 1 < r;){int mid = (l + r) / 2;int smid = sign((v - u).det(a[mid % n] - u));if(smid == sl) l = mid;else r = mid;}return l % n;}int get_tangent(point vec){pair<long double, int> ret = get_tangent(upper, vec);ret.second = (ret.second + (int)lower.size() - 1) % n;ret = max(ret, get_tangent(lower, vec));return ret.second;}bool get_intersection(point u, point v, int &i0, int &i1){int p0 = get_tangent(u - v), p1 = get_tangent(v - u);if(sign((v - u).det(a[p0] - u)) * sign((v - u).det(a[p1] - u)) < 0){if(p0 > p1) swap(p0, p1);i0 = binary_search(u, v, p0, p1);i1 = binary_search(u, v, p1, p0 + n);return true;}else{return false;}} }; int n; point p[N]; vector<point> a, b; Convex D; int m; long double A, B, C;long double cal(int i0) {return fabs((A * D.a[i0].x + B * D.a[i0].y + C) ); } const double INF = 1e9; int main() {scanf("%d", &n);for(int i = 0; i < n; i ++) {//scanf("%lf%lf", &p[i].x, &p[i].y);double x, y;scanf("%lf%lf", &x, &y);p[i].x = x; p[i].y = y;//a.push_back(p[i]);}for(int i = n - 1; i >= 0; i --) a.push_back(p[i]);int ptr = 0;for(int i = 1; i < n; i ++){if(a[ptr] < a[i]) ptr = i;}for(int i = ptr; i < n; i ++){b.push_back(a[i]);}for(int i = 0; i < ptr; i ++){b.push_back(a[i]);}D = Convex(b);scanf("%d", &m);for(int i = 1; i <= m; i ++){double AA, BB, CC;scanf("%lf%lf%lf", &AA, &BB, &CC);A = AA; B = BB; C = CC;double ans = 1e18;int i0, i1;point p0, p1;if(A){p0.y = 0, p0.x = -C / A;p1.y = INF, p1.x = (- C - B * INF) / A;}else if(B){p0.x = 0, p0.y = -C / B;p1.x = INF, p1.y = (-C - INF * A) / B;}//else while(1);if(D.get_intersection(p0, p1, i0, i1)){#define next(i) ((i + 1) % n)#define pre(i) ((i - 1 + n) % n)for(int j = 0; j < 10; j ++){gmin(ans, cal(i0));i0 = next(i0);}for(int j = 0; j < 20; j ++){gmin(ans, cal(i0));i0 = pre(i0);}for(int j = 0; j < 10; j ++){gmin(ans, cal(i1));i1 = next(i1);}for(int j = 0; j < 20; j ++){gmin(ans, cal(i1));i1 = pre(i1);}}else{//ans = 0;//while(1);for(int j = 0; j < n; j ++) gmin(ans, cal(j));}double ANS = ans / sqrt(A * A + B * B);printf("%.6f\n", ANS);}return 0; } /* 【trick&&吐槽】4 1 3 3 1 1 -1 -1 1 1 0 4 -5 【題意】【分析】【時間復雜度&&優化】*/

　　

M. MIPT Campus

留坑。

?

轉載于:https://www.cnblogs.com/clrs97/p/7675261.html

總結

以上是生活随笔為你收集整理的XIII Open Grodno SU Championship的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。