UVA 11722二维线性规划

 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<s1 && bx<=t2;
12 aim1=0;//否则
13 aim2=0.5*(s2-ay)*(bx-t1),cy<=s2 && dx>=t1;
14 aim2=0.5*((t1-w-s1)+(cy-s1))*(t2-t1), cy<=s2 && dx<t1;
15 aim2=0.5*(t2-(s2+w)+(t2-dx))*(s2-s1),cy>s2 && dx<=t1;
16 aim2=0;//否则
17 aim=((s2-s1)*(t2-t1)-aim1-aim2)/(s2-s1)*(t2-t1);
18 */
19 
20 #include<iostream>
21 #include<stdio.h>
22 #include<string.h>
23 #include<algorithm>
24 #include<stdlib.h>
25 #include<math.h>
26 #include<queue>
27 #include<vector>
28 #include<map>
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<s1 && bx<=t2) aim1=0.5*(s1-w-t1+(bx-t1))*(s2-s1);
50         else aim1=0;
51         if (cy<=s2 && dx>=t1) aim2=0.5*(s2-ay)*(bx-t1);
52         else if (cy<=s2 && dx<t1) aim2=0.5*((t1-w-s1)+(cy-s1))*(t2-t1);
53         else if (cy>s2 && dx<=t1) aim2=0.5*(t2-(s2+w)+(t2-dx))*(s2-s1);
54         else aim2=0;
55         cout<<aim1<<" "<<aim2<<" "<<endl;
56         aim=((s2-s1)*(t2-t1)-aim1-aim2)/((s2-s1)*(t2-t1)+0.0);
57         printf("Case #%d: %.7lf
",cas,aim);
58     }
59     return 0;
60 }