UVA 11722二维线性规划-白红宇

UVA 11722二维线性规划

阅读量：4356 次

发布时间：2019-06-07

本文共 1361 字，大约阅读时间需要 4 分钟。

1 /*UVA 11722 2 简单二维线性规划问题： 3 输入：5 integers t1, t2, s1, s2, w (360 ≤ t1 < t2 < 1080, 360 ≤ s1 < s2 < 1080 and 1 ≤ w ≤ 90). 4 目标函数：0<=|s-t|<=w;计算目标的补集更简单 5 步骤：画出坐标轴，注意分类讨论； 6 分类讨论:(图形见书P141) 7 确定4个交点： 8 A(t1,t1+w),B(s2-w,s2),C(t2,t2-w),D(s1+w,s1) 9 aim1=0.5*(s2-ay)*(bx-t1),ay>=s1 && bx<=t2;10 aim1=0.5*((s2-ay)+(s2-(t2+w))*(t2-t1), ay>=s1 && bx>t2;11 aim1=0.5*(s1-w-t1+(bx-t1))*(s2-s1),ay
     
      =t1;14 aim2=0.5*((t1-w-s1)+(cy-s1))*(t2-t1), cy<=s2 && dx
      
       s2 && dx<=t1;16 aim2=0;//否则17 aim=((s2-s1)*(t2-t1)-aim1-aim2)/(s2-s1)*(t2-t1);18 */19 20 #include
       
        21 #include
        
         22 #include
         
          23 #include
          
           24 #include
           
            25 #include
            
             26 #include
             
              27 #include
              
               28 #include
               29 30 using namespace std;31 32 33 int t1,t2,s1,s2,w;34 int ax,ay,bx,by,cx,cy,dx,dy;35 double aim,aim1,aim2;36 int main()37 {38 int t;39 cin>>t;40 for(int cas=1;cas<=t;cas++)41 {42 cin>>t1>>t2>>s1>>s2>>w;43 ax=t1,ay=t1+w;44 bx=s2-w,by=s2;45 cx=t2,cy=t2-w;46 dx=s1+w,dy=s1;47 if (ay>=s1 && bx<=t2) aim1=0.5*(s2-ay)*(bx-t1);48 else if (ay>=s1 && bx>t2) aim1=0.5*((s2-ay)+(s2-(t2+w)))*(t2-t1);49 else if (ay
                
                 =t1) aim2=0.5*(s2-ay)*(bx-t1);52 else if (cy<=s2 && dx
                 
                  s2 && dx<=t1) aim2=0.5*(t2-(s2+w)+(t2-dx))*(s2-s1);54 else aim2=0;55 cout<
                  
                   <<" "<
                   
                    <<" "<