bzoj1027

感觉网上很多题解写的似乎不清楚，这里说一下我的思路
显然对于每个用户的材料（设其比例为Ai,Bi,Ci），
我们要么最多用3种原料（设其比例为ai,bi,ci）混合成需要材料，要么一定混合不成，具体原因往下看
我们设这3种原料所取比例为x1,x2,x3，可得
x1*a1+x2*a2+x3*a3=Ai
x1*b1+x2*b2+x3*b3=Bi
x1*(1-a1-b1)+x2*(1-a2-b2)+x3*(1-a3-b3)=1-Ai-Bi
整理第三个式子可得x1+x2+x3=1 x3=1-x1-x2 (注意这里x1,x2,x3>=0)
带回到前两个式子可得
x1*a1+x2*a2+(1-x1-x2)*a3=Ai
x1*b1+x2*b2+(1-x1-x2)*b3=Bi
整理可得
x1*(a1-a3)+x2*(a2-a3)=Ai-a3
x1*(b1-b3)+x2*(b2-b3)=Bi-b3
看到这个式子大家仔细想就会发现，这其实就是：
向量(a1-a3,b1-b3)和(a2-a3,b2-b3)能否表示向量(Ai-a3,Bi-b3)
根据平面向量的理论我们知道上面的结论是正确的
学过向量的同学可能还会听过这样一个结论（很好证）
设OABC四点，B在线段AC上，O不与ABC共线
则向量OB=a向量OA+b向量OC 一定满足a+b=1 而这里我们的要求也是x1+x2<=1
也就是如果把ai,bi和A,B看做材料点(ai,bi)和原料点(Ai,Bi)
如果用户所需材料i能被原料融合，当且仅当存在三个原料点构成的三角形能把材料点围起来
于是下面的思路就很明显了，我们先求出原料点所组成的凸包，如果所有用户都在凸包内则有解否则无解
接下来我们要找的是最少凸包上的点组成的多边形就能把所有原料点包含了
首先我们要理解什么是包含，我们从凸包一点出发，沿着下凸线到上凸线的顺序走回起点
这样凸包上的每条边就是一个向量，包含的意思就是：每个原料点都必须在每个向量的左边（叉积判断）
于是这就好办了，于是我们穷举向量的起点i终点j，如果所有原料点都在这个向量的左边那么d[i,j]=1 否则d[i,j]=inf
下面我们只要求出一个最小环即可，这可以用floyd搞定
注意这里凸包上是不能存在三点共线的
比较恶心的是这道题要注意精度问题

 const eps=1e-10;

 type point=record

        x,y:double;

      end;

 var a,b:array[..] of point;

     w:array[..] of longint;

     f:array[..,..] of longint;

     ans,i,j,k,p,n,m:longint;

     ch:boolean;

 function min(a,b:longint):longint;

   begin

     if a>b then exit(b) else exit(a);

   end;

 procedure swap(var a,b:point);

   var c:point;

   begin

     c:=a;

     a:=b;

     b:=c;

   end;

 procedure sort(l,r:longint);

   var i,j:longint;

       p:point;

   begin

     i:=l;

     j:=r;

     p:=a[(l+r) shr ];

     repeat

       while (a[i].x<p.x) or (a[i].x=p.x) and (a[i].y<p.y) do inc(i);

       while (p.x<a[j].x) or (a[j].x=p.x) and (p.y<a[j].y) do dec(j);

       if not(i>j) then

       begin

         swap(a[i],a[j]);

         inc(i);

         dec(j);

       end;

     until i>j;

     if l<j then sort(l,j);

     if i<r then sort(i,r);

   end;

 function cross(a,b,c:point):double;

   begin

     exit((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y));

   end;

 function check:boolean;

   var i,j:longint;

   begin

     dec(k);

     for i:= to k do

       for j:= to n do

         if cross(a[w[i]],a[w[i+]],b[j])<-eps then exit(false);

     exit(true);

   end;

 begin

   readln(m,n);

   for i:= to m do

     readln(a[i].x,a[i].x,a[i].y);

   for i:= to n do

     readln(b[i].x,b[i].x,b[i].y);

   if n= then

   begin

     writeln();

     halt;

   end;

   for i:= to m do

   begin

     ch:=true;

     for j:= to n do

       if (a[i].x<>b[j].x) or (a[i].y<>b[j].y) then

       begin

         ch:=false;

         break;

       end;

     if ch then //这里特判一下

     begin

       writeln();

       halt;

     end;

   end;

   sort(,m);

   k:=;

   w[]:=;

   for i:= to m do

   begin

     while (k>) and (cross(a[w[k-]],a[w[k]],a[i])<eps) do dec(k);

     inc(k); w[k]:=i;

   end;

   j:=k;

   for i:=m- downto  do

   begin

     while (k>j) and (cross(a[w[k-]],a[w[k]],a[i])<eps) do dec(k);

     inc(k); w[k]:=i;

   end;

   if check then

   begin

     for i:= to k do

       for j:= to k do

       begin

         f[i,j]:=m;

         if i<>j then

         begin

           ch:=true;

           for p:= to n do

             if cross(a[w[i]],a[w[j]],b[p])<-eps then

             begin

               ch:=false;

               break;

             end;

           if ch then f[i,j]:=;

         end;

       end;

     for p:= to k do

       for i:= to k do

         for j:= to k do

           f[i,j]:=min(f[i,j],f[i,p]+f[p,j]);

     ans:=m;

     for i:= to k do

       ans:=min(ans,f[i,i]);

     writeln(ans);

   end

   else writeln(-);

 end.

巴特西

bzoj1027

最新文章

热门文章