欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

220专项:C. Mice problem(几何)

程序员文章站 2022-03-30 08:24:22
...

原题: http://codeforces.com/problemset/problem/793/C

题意:

有一个矩形,n个点,告诉每个点的位置和其延x轴y轴移动的速度,问最少多少时间后这个矩形可以框住这n个点(严格)。

解析:

求出每个点运动到这个矩形内的时间的区间,求一个区间交。如果不存在或是一个点(说明蹭过去了),就说明不行。

区间求法:

  1. 对于内部的点,求出速度方向上x的时间和y的时间取一个min即可。
  2. 对于外部的点比较麻烦。对于点做矩形的四个边的接触的时间,不行就是1e9。然后对非1e9时间做一个unique,就是两个时间了(因为可能从一个点进来,那么会有两个时间是相同的)。
#include<bits/stdc++.h>
using namespace std;

const int maxn=100009;
const double eps=1e-14;
struct Point{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
}sp,ep,e[maxn],v[maxn],sp2,ep2;
double l[maxn],r[maxn];

inline int dcmp(double x){
    return fabs(x)<eps?0:(x>0?1:-1);
}
inline bool in(int i){
    if(e[i].x>=sp.x&&e[i].x<=ep.x&&e[i].y>=sp.y&&e[i].y<=ep.y)return 1;
    return 0;
}

double deal(Point p,Point v,Point a,Point b){
    if(a.y==b.y&&((p.y<a.y&&v.y<0)||(p.y>a.y&&v.y>0))){//反方向
        return 1e9;
    }
    if(a.x==b.x&&((p.x<a.x&&v.x<0)||(p.x>a.x&&v.x>0))){//反方向
        return 1e9;
    }
    if(a.x==b.x){//是否落在区间内
        double t=fabs((p.x-a.x)/v.x);
        double y=p.y+t*v.y;
        if(dcmp(max(a.y,b.y)-y)>=0&&dcmp(min(a.y,b.y)-y)<=0)return t;
        return 1e9;
    }
    else{
        double t=fabs((p.y-a.y)/v.y);
        double x=p.x+t*v.x;
        if(dcmp(max(a.x,b.x)-x)>=0&&dcmp(min(a.x,b.x)-x)<=0)return t;
        return 1e9;
    }
}

int main(){
    int n;scanf("%d",&n);
    scanf("%lf%lf%lf%lf",&sp.x,&sp.y,&ep.x,&ep.y);
    sp2=sp,sp2.y=ep.y;
    ep2=ep,ep2.y=sp.y;
    for(int i=1;i<=n;i++){
        scanf("%lf%lf%lf%lf",&e[i].x,&e[i].y,&v[i].x,&v[i].y);
        if(e[i].x==sp.x&&v[i].x==0){
            return 0*printf("-1\n");
        }
        if(e[i].x==ep.x&&v[i].x==0){
            return 0*printf("-1\n");
        }
        if(e[i].y==sp.y&&v[i].y==0){
            return 0*printf("-1\n");
        }
        if(e[i].y==ep.y&&v[i].y==0){
            return 0*printf("-1\n");
        }
    }

    for(int i=1;i<=n;i++){
        if(in(i)){
            double tx,ty;
            l[i]=0;
            if(dcmp(v[i].x)==0){
                tx=1e9;
            }
            else if(v[i].x>0){
                tx=(ep.x-e[i].x)/v[i].x;
            }
            else{
                tx=(sp.x-e[i].x)/v[i].x;
            }

            if(dcmp(v[i].y)==0){
                ty=1e9;
            }
            else if(v[i].y>0){
                ty=(ep.y-e[i].y)/v[i].y;
            }
            else{
                ty=(sp.y-e[i].y)/v[i].y;
            }
            r[i]=min(fabs(tx),fabs(ty));
        }
        else{
            double t[4];
                t[0]=fabs(deal(e[i],v[i],sp,sp2)),
                t[1]=fabs(deal(e[i],v[i],sp2,ep)),
                t[2]=fabs(deal(e[i],v[i],sp,ep2)),
                t[3]=fabs(deal(e[i],v[i],ep,ep2));
            sort(t,t+4);
            int ar=-1;
            for(int i=0;i<4;i++){
                if(t[i]==1e9)break;
                ar++;
            }
            if(ar==-1)l[i]=1e9,r[i]=1e9;
            else{
                int ar2=0;
                for(int i=1;i<=ar;i++){
                    if(dcmp(t[i]-t[ar2])==0)continue;
                    else{
                        t[++ar2]=t[i];
                    }
                }
                if(ar2==0){
                    l[i]=r[i]=t[0];
                }
                else{
                    l[i]=t[0];
                    r[i]=t[1];
                }
            }
        }
    }
    double L=-1,R=1e9;
    for(int i=1;i<=n;i++){
        L=max(l[i],L);
        R=min(r[i],R);
    }
    if(dcmp(L-R)>0||L==1e9||dcmp(L-R)==0)printf("-1\n");
    else printf("%.20f\n",L);
}