码农题：边分治+闵可夫斯基和

发现，每一条路径是一个ax+b的一次函数形式

最暴力的想法是：

把所有的路径拿出来，贡献给每个t

发现，其实是这些直线的半平面交（从上往下看能看到的直线）

 

考虑能不能不n^2

各种取max，合并，覆盖，都可以减少不必要的枚举

 

本题，考虑边分治

考虑所有经过当前中心边的路径

 

但是半平面交无法合并，所以用到一个结论：半平面交和凸包对偶：ax+b->(a,b)求上凸壳即可。

因为，凸壳可以合并！

 

所以，左边求出来，右边求出来，合并即可。恰好ax+b+cx+d=(a+c,b+d)

闵可夫斯基和：

 

这样，总点数是O(nlogn)的，最后所有可能贡献的点再求一个凸包，

答案，就是用-x去切凸包，最大化斜率

单指针扫一下即可。

 

注意：

vis数组4倍

闵可夫斯基和是n+m-1步！！！！（调了2h）

 

代码：

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
      
       using namespace std;typedef long long ll;template
       
        il void rd(T &x){    char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}template
        
         il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Modulo{const int mod=998244353;int ad(int x,int y){ return (x+y)>=mod?x+y-mod:x+y;}void inc(int &x,int y){x=ad(x,y);}int mul(int x,int y){ return (ll)x*y%mod;}void inc2(int &x,int y){x=mul(x,y);}int qm(int x,int y=mod-2){ int ret=1;while(y){ if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}}//using namespace Modulo;namespace Miracle{const int N=100000+5;const int inf=0x3f3f3f3f;int n,m;struct node{ int nxt,to; ll a,b; node(){} node(ll aa,ll bb,int y){ a=aa;b=bb;to=y;nxt=0; }}e[4*N];vector
           
            to[N];int hd[2*N],cnt=1;void add(int x,int y,int a,int b){ // cout<<" link "<
            
             <<" "<
             
              <
              
               1&&cross(f[i]-tmp[nc],f[i]-tmp[nc-1])<=0) --nc; tmp[++nc]=f[i]; } } for(reg i=1;i<=nc;++i) f[i]=tmp[i]; n=nc;}void merge(po *f,int n,po *g,int m){ //add to q //min ke fu si ji sum int pf=1,pg=1; for(reg i=1;i<=n+m-1;++i){ q[++size]=(f[pf]+g[pg]); if(pf==n) ++pg; else if(pg==m) ++pf; else{ long double cha=cross(f[pf]+g[pg+1]-q[size],f[pf+1]+g[pg]-q[size]); if(cha<=0) ++pg; else ++pf; } }}bool vis[4*N];//bian!!!int mi;void dfs(int x,int fa){ //warning!! n is 2*n!!!! sz[x]=1; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa||vis[i]) continue; dfs(y,x); if(max(sz[y],nowsz-sz[y])
               
                (q[ptr].x*i+q[ptr].y)){ ++ptr; } ll ans=q[ptr].x*i+q[ptr].y; ot(ans); } return 0;}}signed main(){ Miracle::main(); return 0;}/* Author: *Miracle**/
               
              
             
            
           
          
         
        
       
      
     

其实挺套路的吧，，

路径太多，考虑覆盖一些东西。

半平面交转凸壳，这个是合并的前提，然后就边分治了。