Codeforces 793C

题目链接：http://codeforces.com/problemset/problem/793/C

题目大意：给你一个捕鼠器坐标，和各个老鼠的的坐标以及相应坐标的移动速度，问你是否存在一个时间点可以关闭捕鼠器抓住所有的老鼠，误差不能超过1e-6。

解题思路：可以把每个老鼠进入捕鼠器的时间和出捕鼠器的时间计算出来，那就可以把一只进出捕鼠器时间当成一个集合，把各个集合求交集得到的就是最后可以捕到所有老鼠的时间范围，再取交集左边界时间就可以了。

千万要注意一点：老鼠不能在边界上被捕捉，表示之前没看到足足想了一个小时。。。

所以最后得出来的时间集合的左边界l肯定是不能等于右边界r的，所以要判定r-l>=1e-11，取1e-11是为了提高精度。

如下面这一组样例：　　

1
99998 99998 99999 99999
0 0 99999 100000
最后得出的l=0.9999899999 r=0.9999900000
如果只取到1e-7的话那四舍五入后l和r相等都是0.9999900，这显然错误了，所以精度尽可能取高一点。

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 double l=0,r=1e11;
 5 
 6 void updata(int pos,int lb,int rb,int v){
 7     if(v==0){
 8         if(pos>lb&&pos<rb) 
 9             return;
10         r=-1;
11     }
12     double t1=(double)(lb-pos)/v,t2=(double)(rb-pos)/v;
13     if(t1>t2)
14         swap(t1,t2);
15     l=max(l,t1);
16     r=min(r,t2);
17 }
18 
19 int main(){
20     int n;
21     int x1,y1,x2,y2;
22     scanf("%d",&n);
23     scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
24     for(int i=1;i<=n;i++){
25         int x,y,vix,viy;
26         scanf("%d %d %d %d",&x,&y,&vix,&viy);
27         updata(x,x1,x2,vix);
28         updata(y,y1,y2,viy);        
29     }    
30     if(r-l>=1e-11&&r>0)
31         printf("%.10lf
",l);
32     else
33         printf("-1
");
34     return 0;
35 }