2019.6.1 模拟赛——[ 费用流 ][ 数位DP ][ 计算几何 ]

第一题：http://codeforces.com/contest/1061/problem/E

　　把点集分成不相交的，然后跑费用流即可。然而错了一个点。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

int Mn(int a,int b){return a<b?a:b;}

const int N=,M=N*,INF=N;

int n,tot,hd[N],xnt=,to[M],nxt[M],cap[M],w[M];

int dis[N],info[N],pre[N]; bool ins[N];

int S,T,flow,val,ans; bool fg;

queue<int> q;

void add(int x,int y,int z,int k)

{

  to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;

  cap[xnt]=z; w[xnt]=k;

  to[++xnt]=x;nxt[xnt]=hd[y];hd[y]=xnt;

  cap[xnt]=; w[xnt]=-k;

}

namespace I{

  const int N=,M=N<<;

  int c[N],hd[N],xnt,to[M],nxt[M],fa[N];

  int h2[N],xt2,t2[M],nt2[M];

  int lm[N],q[N],he,tl,tmp;

  void ad1(int x,int y)

  {to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}

  void ad2(int x,int y)

  {t2[++xt2]=y;nt2[xt2]=h2[x];h2[x]=xt2;}

  void ini_dfs(int cr,int f)

  {

    fa[cr]=f;

    for(int i=hd[cr],v;i;i=nxt[i])

      if((v=to[i])!=f) ini_dfs(v,cr);

  }

  void dfs(int cr)

  {

    add(tot,cr,,c[cr]);

    for(int i=hd[cr],v;i;i=nxt[i])

      if((v=to[i])!=fa[cr])

    {

      if(lm[v]){q[++tl]=v; tmp-=lm[v];}

      else dfs(v);

    }

  }

  void ini_dfs2(int cr,int f)

  {

    fa[cr]=f;

    for(int i=h2[cr],v;i;i=nt2[i])

      if((v=t2[i])!=f) ini_dfs2(v,cr);

  }

  void dfs2(int cr)

  {

    add(cr,tot,,);

    for(int i=h2[cr],v;i;i=nt2[i])

      if((v=t2[i])!=fa[cr])

    {

      if(lm[v]){q[++tl]=v; tmp-=lm[v];}

      else dfs2(v);

    }

  }

  void solve()

  {

    int s0=rdn(),s1=rdn();

    for(int i=;i<=n;i++)c[i]=rdn();

    for(int i=,u,v;i<n;i++)

      u=rdn(),v=rdn(),ad1(u,v),ad1(v,u);

    for(int i=,u,v;i<n;i++)

      u=rdn(),v=rdn(),ad2(u,v),ad2(v,u);

    int Q=rdn();

    for(int i=;i<=Q;i++)

      {int d=rdn(); lm[d]=rdn();}

    val=lm[s0];

    he=tl=; q[++tl]=s0; ini_dfs(s0,);

    while(he<tl)

      {

    int k=q[++he]; tmp=lm[k];

    tot++; dfs(k); add(S,tot,tmp,);

      }

    memset(lm,,sizeof lm); Q=rdn();

    for(int i=;i<=Q;i++)

      {int d=rdn(); lm[d]=rdn();}

    he=tl=; q[++tl]=s1; fa[s1]=; ini_dfs2(s1,);

    while(he<tl)

      {

    int k=q[++he]; tmp=lm[k];

    tot++; dfs2(k); add(tot,T,tmp,);

      }

    if(val!=lm[s1])fg=;

  }

}

bool spfa()

{

  memset(dis,-,sizeof dis); dis[S]=;

  info[S]=INF; info[T]=; q.push(S); ins[S]=;

  while(q.size())

    {

      int k=q.front(); q.pop(); ins[k]=;

      for(int i=hd[k],v;i;i=nxt[i])

    if(cap[i]&&dis[v=to[i]]<dis[k]+w[i])

      {

        dis[v]=dis[k]+w[i]; pre[v]=i;

        info[v]=Mn(info[k],cap[i]);

        if(!ins[v])ins[v]=,q.push(v);

      }

    }

  return info[T];

}

void ek()

{

  int k=info[T]; flow+=k;

  for(int i=pre[T];i;i=pre[to[i^]])

    { cap[i]-=k; cap[i^]+=k; ans+=k*w[i];}

}

int main()

{

  freopen("w.in","r",stdin);

  freopen("w.out","w",stdout);

  tot=n=rdn(); S=; T=++tot; I::solve();

  if(fg){puts("-1");return ;}

  while(spfa())ek();

  if(flow==val)printf("%d\n",ans);

  else puts("-1");

  return ;

}

囧

　　后来发现是题目里写了 “每个人的条件不会自相矛盾” ，但那个点却自相矛盾了。

　　判一下即可。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

int Mn(int a,int b){return a<b?a:b;}

const int N=,M=N*,INF=N;

int n,tot,hd[N],xnt=,to[M],nxt[M],cap[M],w[M];

int dis[N],info[N],pre[N]; bool ins[N];

int S,T,flow,val,ans; bool fg;

queue<int> q;

void add(int x,int y,int z,int k)

{

  to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;

  cap[xnt]=z; w[xnt]=k;

  to[++xnt]=x;nxt[xnt]=hd[y];hd[y]=xnt;

  cap[xnt]=; w[xnt]=-k;

}

namespace I{

  const int N=,M=N<<;

  int c[N],hd[N],xnt,to[M],nxt[M],fa[N];

  int h2[N],xt2,t2[M],nt2[M];

  int lm[N],q[N],he,tl,tmp;

  void ad1(int x,int y)

  {to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}

  void ad2(int x,int y)

  {t2[++xt2]=y;nt2[xt2]=h2[x];h2[x]=xt2;}

  void ini_dfs(int cr,int f)

  {

    fa[cr]=f;

    for(int i=hd[cr],v;i;i=nxt[i])

      if((v=to[i])!=f) ini_dfs(v,cr);

  }

  void dfs(int cr)

  {

    add(tot,cr,,c[cr]);

    for(int i=hd[cr],v;i;i=nxt[i])

      if((v=to[i])!=fa[cr])

    {

      if(lm[v]){q[++tl]=v; tmp-=lm[v];}

      else dfs(v);

    }

  }

  void ini_dfs2(int cr,int f)

  {

    fa[cr]=f;

    for(int i=h2[cr],v;i;i=nt2[i])

      if((v=t2[i])!=f) ini_dfs2(v,cr);

  }

  void dfs2(int cr)

  {

    add(cr,tot,,);

    for(int i=h2[cr],v;i;i=nt2[i])

      if((v=t2[i])!=fa[cr])

    {

      if(lm[v]){q[++tl]=v; tmp-=lm[v];}

      else dfs2(v);

    }

  }

  void solve()

  {

    int s0=rdn(),s1=rdn();

    for(int i=;i<=n;i++)c[i]=rdn();

    for(int i=,u,v;i<n;i++)

      u=rdn(),v=rdn(),ad1(u,v),ad1(v,u);

    for(int i=,u,v;i<n;i++)

      u=rdn(),v=rdn(),ad2(u,v),ad2(v,u);

    int Q=rdn();

    for(int i=;i<=Q;i++)

      {int d=rdn(); lm[d]=rdn();}

    val=lm[s0];

    he=tl=; q[++tl]=s0; ini_dfs(s0,);

    while(he<tl)

      {

    int k=q[++he]; tmp=lm[k];

    tot++; dfs(k); if(tmp<){fg=;break;}

    add(S,tot,tmp,);

      }

    if(fg)return;

    memset(lm,,sizeof lm); Q=rdn();

    for(int i=;i<=Q;i++)

      {int d=rdn(); lm[d]=rdn();}

    he=tl=; q[++tl]=s1; fa[s1]=; ini_dfs2(s1,);

    while(he<tl)

      {

    int k=q[++he]; tmp=lm[k];

    tot++; dfs2(k); if(tmp<){fg=;break;}

    add(tot,T,tmp,);

      }

    if(val!=lm[s1])fg=;

  }

}

bool spfa()

{

  memset(dis,-,sizeof dis); dis[S]=;

  info[S]=INF; info[T]=; q.push(S); ins[S]=;

  while(q.size())

    {

      int k=q.front(); q.pop(); ins[k]=;

      for(int i=hd[k],v;i;i=nxt[i])

    if(cap[i]&&dis[v=to[i]]<dis[k]+w[i])

      {

        dis[v]=dis[k]+w[i]; pre[v]=i;

        info[v]=Mn(info[k],cap[i]);

        if(!ins[v])ins[v]=,q.push(v);

      }

    }

  return info[T];

}

void ek()

{

  int k=info[T]; flow+=k;

  for(int i=pre[T];i;i=pre[to[i^]])

    { cap[i]-=k; cap[i^]+=k; ans+=k*w[i];}

}

int main()

{

  freopen("w.in","r",stdin);

  freopen("w.out","w",stdout);

  tot=n=rdn(); S=; T=++tot;

  I::solve();

  if(fg){puts("-1");return ;}

  while(spfa())ek();

  if(flow==val)printf("%d\n",ans);

  else puts("-1");

  return ;

}

第二题：http://codeforces.com/contest/1045/problem/H

　　考场上不会做……

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

using namespace std;

const int N=,mod=1e9+;

int upt(int x){while(x>=mod)x-=mod;while(x<)x+=mod;return x;}

int n,m,A,B,C,D,ans;char s1[N],s2[N],s[N];

struct Node{

  int x,y;

  Node(int x=,int y=):x(x),y(y) {}

  bool operator< (const Node &b)const

  {return x==b.x?y<b.y:x<b.x;}

};

map<Node,int> dp[N][][N][N],mp[N][][N][N];

void init()

{

  memcpy(s,s1,sizeof s1);

  for(int i=;i<=n;i++)

    if(s[i]==''){s[i]='';break;}

    else s[i]='';

}

int dfs(int t,bool fx,int a,int b,int c,int d)

{

  if(a<||b<||c<||d<)return ;

  Node cr=Node(c,d);

  if(dp[t][fx][a][b].count(cr))

    {

      return dp[t][fx][a][b][cr];

    }

  if(!t) return dp[t][fx][a][b][cr]=((!a)&&(!b)&&(!c)&&(!d));

  int ret=;

  if(!fx)

    {

      ret=upt(ret+dfs(t-,,a-,b,c,d));

      ret=upt(ret+dfs(t-,,a,b-,c,d));

    }

  else

    {

      ret=upt(ret+dfs(t-,,a,b,c-,d));

      ret=upt(ret+dfs(t-,,a,b,c,d-));

    }

  dp[t][fx][a][b][cr]=ret; return ret;

}

int dfsx(int t,bool fx,int a,int b,int c,int d)

{

  if(a<||b<||c<||d<)return ;

  Node cr=Node(c,d);

  if(mp[t][fx][a][b].count(cr))

    {

      return mp[t][fx][a][b][cr];

    }

  if(!t)

    {

      int ret=((!a)&&(!b)&&(!c)&&(!d));

      return mp[t][fx][a][b][cr]=ret;

    }

  if(s[t]=='')

    {

      if(!fx)a--; else c--;

      int ret=dfsx(t-,,a,b,c,d);

      return mp[t][fx][a][b][cr]=ret;

    }

  int ta=a,tb=b,tc=c,td=d; if(!fx)tb--; else td--;

  int ret=dfsx(t-,,ta,tb,tc,td);

  ta=a; tb=b; tc=c; td=d;

  if(!fx)a--; else c--;

  ret=upt(ret+dfs(t-,,a,b,c,d));//

  mp[t][fx][a][b][cr]=ret; return ret;

}

void solve(int lm)

{

  for(int t=;t<=lm;t++)

    for(int fx=;fx<=;fx++)

      for(int i=;i<=A;i++)

    for(int j=;j<=B;j++)

      {

        dp[t][fx][i][j].clear();

        mp[t][fx][i][j].clear();

      }

  for(int t=;t<lm;t++)

    {

      ans=upt(ans+dfs(t-,,A,B,C,D));

    }

  ans=upt(ans+dfsx(lm-,,A,B,C,D));

}

int main()

{

  freopen("i.in","r",stdin);

  freopen("i.out","w",stdout);

  scanf("%s",s1+); scanf("%s",s2+);

  n=strlen(s1+); m=strlen(s2+);

  reverse(s1+,s1+n+); reverse(s2+,s2+m+);

  scanf("%d%d%d%d",&A,&B,&C,&D);

  init(); solve(n); ans=upt(-ans);

  memcpy(s,s2,sizeof s2);

  solve(m); printf("%d\n",ans);

  return ;

}

囧

　　后来得知 “随便填” 的方案可以用组合数算。就是通过 01 和 10 的个数可以知道 0 和 1 分成了几段。

　　仔细一想，直接搜，不用记忆化就行。

　　不知为何自己的代码必须特判 if( B<C-1 || B>C ) puts(" 0 ");

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

int Mx(int a,int b){return a>b?a:b;}

int Mn(int a,int b){return a<b?a:b;}

const int N=1e5+,mod=1e9+;

int upt(int x){while(x>=mod)x-=mod;while(x<)x+=mod;return x;}

int pw(int x,int k)

{int ret=;while(k){if(k&)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=;}return ret;}

int n,A,B,C,D,jc[N],jcn[N];

char s[N],s1[N],s2[N];

struct Node{

  int a,b,c,d;

  Node(int a=,int b=,int c=,int d=):a(a),b(b),c(c),d(d) {}

  bool operator< (const Node &v)const

  {

    if(a!=v.a)return a<v.a; if(b!=v.b)return b<v.b;

    if(c!=v.c)return c<v.c; return d<v.d;

  }

};

void init()

{

  memcpy(s,s1,sizeof s1);

  for(int i=;i<=n;i++)

    if(s[i]=='')s[i]='';

    else {s[i]='';if(i==n)n--;break;}

  int lm=1e5;//not Mx(A,B,C,D) for *2

  jc[]=;for(int i=;i<=lm;i++)jc[i]=(ll)jc[i-]*i%mod;

  jcn[lm]=pw(jc[lm],mod-);

  for(int i=lm-;i>=;i--)jcn[i]=(ll)jcn[i+]*(i+)%mod;

}

int C2(int n,int m)

{

  if(n==(-)&&m==(-))return ;///

  if(n<||m<||n<m)return ;

  return (ll)jc[n]*jcn[m]%mod*jcn[n-m]%mod;

}

int cal(int t,bool fx,int a,int b,int c,int d)

{

  if(a<||b<||c<||d<)return ;//

  if(!t) return ((!a)&&(!b)&&(!c)&&(!d));

  int t0,t1,c0,c1;

  if(!fx)c0=c+,c1=b; else c0=c,c1=b+;

  if(!fx)t0=a+c0-,t1=d+c1; else t0=a+c0,t1=d+c1-;

  int ret=;

  if(t0+t1==t) ret=(ll)C2(t0-,c0-)*C2(t1-,c1-)%mod;

  c0=c; c1=b; t0=a+c0; t1=d+c1;

  if(t0+t1==t) ret=(ret+(ll)C2(t0-,c0-)*C2(t1-,c1-))%mod;

  return ret;

}

int dfs(int t,bool fx,int a,int b,int c,int d)

{

  if(a<||b<||c<||d<)return ;

  if(!t) return ((!a)&&(!b)&&(!c)&&(!d));

  int ta=a,tb=b,tc=c,td=d;

  if(s[t]=='')

    {

      if(!fx)ta--; else tc--;

      int ret=dfs(t-,,ta,tb,tc,td);

      return ret;

    }

  if(!fx)ta--; else tc--;

  int ret=cal(t-,,ta,tb,tc,td);

  ta=a; tc=c; if(!fx)tb--; else td--;

  ret=upt(ret+dfs(t-,,ta,tb,tc,td));

  return ret;

}

int solve()

{

  int ret=;

  for(int t=;t<n;t++)

    ret=upt(ret+cal(t-,,A,B,C,D));

  if(n)ret=upt(ret+dfs(n-,,A,B,C,D));//if

  return ret;

}

int main()

{

  scanf("%s",s1+); scanf("%s",s2+);

  scanf("%d%d%d%d",&A,&B,&C,&D);

  if(B<C-||B>C){puts("");return ;}///?

  n=strlen(s1+); reverse(s1+,s1+n+);

  init(); int ans=upt(-solve());

  n=strlen(s2+); reverse(s2+,s2+n+);

  memcpy(s,s2,sizeof s2); ans=upt(ans+solve());

  printf("%d\n",ans);

  return ;

}

第三题：http://codeforces.com/contest/780/problem/H

　　题意：给出 n 个点的坐标，第 i 个点和第 i%n+1 个点连线组成一个环，有 m 个动点在环上移动，满足每个动点的速度相同、相邻动点距离相等。

　　　　　求一个最小的 R，满足存在一个时刻，任意相邻点的距离 <= R 。

　　学习了 #52224787（by Idxoi）的 AC 代码。

　　考虑把 “第 i 个点和第 i%m+1 个点的距离” 随时间变化的函数图象画出来。如果两个点分别在两条线上，那么这个图象是一个二次函数。整个图象就是 O(n) 段二次函数接起来。

　　考虑二分答案，那么图象中 y 在 mid 以下部分的 x 都是合法的；该 mid 合法满足存在一个 x ，使得 x , x+T/m , x+2*T/m , ... x+m*T/m 都是合法的（ T 是总长度；即等距的 m 个位置都是合法的）。

　　已知 mid ，对于一段二次函数，易求其在 y=mid 一下部分的 x ，且对于一个二次函数这样的 x 是0/1/2个区间；

　　所以把整个图象分成各个二次函数，然后求出一些合法的 x 区间；再考虑把 T 分成 [ 0 , T/m ] , [ T/m , 2*T/m ] , ... , [ (m-1)*T/m , m*T/m ] ，然后把这 m 个区间里的 “合法 x 区间集合” 都叠起来，如果有一个位置被覆盖了 m 次，那么该 mid 合法。

　　所以把整个图象分成若干段，满足每段是一个二次函数，且每段只在一个 [ 0 , T/m ] , ... , [ (m-1)*T/m , m*T/m ] 这样的区间里；然后对每段求一下合法的 x 区间，用差分的形式记录下来，按位置排序后扫一遍看看有没有被覆盖 m 次的位置即可。

　　注意这个排序是以位置为第一关键字、+1/-1为第二关键字；且要先减后加！

　　注意虽然算的是至多 n*4 段（n*2 个端点，每个区间被 m 的限制切一次，总数再 *2），但空间要再开大。不太知道原因……可能是精度使得多出了一些段？

　　注意二分不要像平常一样写。 mid 是否合法只是影响二分方向，最终的答案不一定是一个合法的 mid ，而是最后二分到的位置。可能是因为精度才这样的？

　　找函数图象的实现方法就是把给出的 n 条线段的长度、方向都预处理出来，然后两个指针卡着两个点 st , en 的位置，每次走到 “ 下一个 [ 0 , T/m ] 这样的段的末端 ”、“ st 所在线段的末端 ” 、 “ en 所在线段的末端 ” 中较近的一个。就是看看哪个长度短，然后 st 、en 就移动到 “当前位置 + 长度×所在线段方向” 的位置。

　　已知两动点 st , en 的当前位置以及移动方向向量（就是所在线段的方向），如何求出距离的二次函数方程？

　　　　考虑 \( st=(a_1+c_1*x , b_1+d_1*x ) , en=(a_2+c_2*x , b_2+d_2*x ) \) （即，\( (a_1,b_1) \) 就是 st 的初始位置， \( (c_1,d_1) \) 是移动方向， x 是时间自变量）

　　　　\( dis^2 = ( (a_1+c_1*x) - (a_2+c_2*x) )^2 + ( ( b_1+d_1*x ) - ( b_2+d_2*x ) )^2 \)（就是平常的 \( dis^2=(x_1-x_2)^2+(y_1-y_2)^2 \)）

　　　　\( dis^2 = ( (c_1-c_2)^2+(d_1-d_2)^2 )x^2 + 2[ (a_1-a_2)(c_1-c_2) + (b_1-b_2)(d_1-d_2) ]x + (a_1-a_2)^2 + (b_1-b_2)^2 \)

　　　　所以可知关于 \(dis^2\) 的二次函数 \( y=a*x^2+b*x+c \) 的系数。要判断 dis<=mid 的部分，就是判断 \(dis^2<=mid^2\) 的部分。

　　注意到二次函数的 a 是 >=0 的，所以可以少讨论一点。

　　注意在求交点的时候判断正负就不要加 eps 了。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define db long double

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

const int N=(3e4+)*; const db eps=1e-;

int dcmp(db x){return (x>-eps)-(x<eps);}

db Sqr(db x){return x*x;}

int n,m,tot,cnt; db len[N];

struct Node{

  db x,y;

  Node(db x=,db y=):x(x),y(y) {}

  Node operator+ (const Node &b)const{return Node(x+b.x,y+b.y);}

  Node operator- (const Node &b)const{return Node(x-b.x,y-b.y);}

  Node operator* (const db &b)const{return Node(x*b,y*b);}

  Node operator/ (const db &b)const{return Node(x/b,y/b);}

  db mod(){ return Sqr(x)+Sqr(y);}

}a[N],dir[N];

db dot(Node u,Node v){return u.x*v.x+u.y*v.y;}

struct Dt{

  db ql,qr,a,b,c;

  Dt(db l=,db r=,db a=,db b=,db c=):ql(l),qr(r),a(a),b(b),c(c) {}

}h[N];

struct F{

  db p;int v;

  F(db p=,int v=):p(p),v(v) {}

  bool operator< (const F &b)const

  {return dcmp(p-b.p)==?v<b.v:p<b.p;}//v<b.v not v>b.v

}tp[N<<];

db chk(db mid)

{

  cnt=;

  for(int i=;i<=tot;i++)

    {

      db a=h[i].a,b=h[i].b,c=h[i].c-mid;//a>=0

      db ql=h[i].ql,qr=h[i].qr;

      if(a<eps)

    {

      if(dcmp(b)==)

        {

          if(c<eps)

        {tp[++cnt]=F(ql,);tp[++cnt]=F(qr,-);}

        }

      else

        {

          db x=-c/b;

          if(b>&&x>)

        {

          tp[++cnt]=F(ql,);

          tp[++cnt]=F(min(ql+x,qr),-);

        }

          else if(b<&&ql+x<qr)

        {

          tp[++cnt]=F(ql+max(x,(db)),);

          tp[++cnt]=F(qr,-);

        }

        }

    }

      else

    {

      db dlt=Sqr(b)-*a*c; if(dlt<)continue;

      dlt=sqrt(dlt); db tmp=*a;

      db x0=ql+(-b-dlt)/tmp, x1=ql+(-b+dlt)/tmp;

      x0=max(x0,ql); x1=min(x1,qr);

      if(x0<x1)

        {

          tp[++cnt]=F(x0,);tp[++cnt]=F(x1,-);

        }

    }

    }

  sort(tp+,tp+cnt+);

  for(int i=,lj=;i<=cnt;i++)

    { lj+=tp[i].v; if(lj==m)return true;}

  return false;

}

void cz(int &x){ x++; if(x>n)x=;}

int main()

{

  n=rdn();m=rdn();

  for(int i=;i<=n;i++)a[i].x=rdn(),a[i].y=rdn();

  a[n+]=a[]; db sm=;

  for(int i=;i<=n;i++)

    {

      len[i]=sqrt((a[i+]-a[i]).mod()); sm+=len[i];

      dir[i]=(a[i+]-a[i])/len[i];

    }

  db ave=sm/m,L=len[],R=ave,nw=; int id=;//nw=0 not ave

  int pl=,pr=;

  for(;dcmp(R-len[pr])>=;pr++)R-=len[pr];

  Node st=a[],en=a[pr]+dir[pr]*R; R=len[pr]-R;

  while(dcmp(sm-nw)>)

    {

      db cr=min(id*ave-nw,min(L,R));

      Node d0=en-st,d1=dir[pr]-dir[pl];

      st=st+dir[pl]*cr; en=en+dir[pr]*cr;//after d0,d1

      h[++tot]=Dt(nw-(id-)*ave,nw-(id-)*ave+cr,

          d1.mod(),*dot(d0,d1),d0.mod());

      L-=cr; if(dcmp(L)==){cz(pl);st=a[pl];L=len[pl];}

      R-=cr; if(dcmp(R)==){cz(pr);en=a[pr];R=len[pr];}

      //cz(pl) not ++pl

      nw+=cr; if(dcmp(id*ave-nw)==)id++;//<= not ==

    }

  db l=,r=ave;

  while(r-l>eps)

    {

      db mid=(l+r)/;

      if(chk(Sqr(mid)))r=mid;

      else l=mid;

    }

  printf("%.10Lf\n",l);//l not ans

  return ;

}

巴特西

2019.6.1 模拟赛——[ 费用流 ][ 数位DP ][ 计算几何 ]

最新文章

热门文章