220专项:C. Mice problem(几何)
程序员文章站
2022-03-30 08:24:22
...
原题: http://codeforces.com/problemset/problem/793/C
题意:
有一个矩形,n个点,告诉每个点的位置和其延x轴y轴移动的速度,问最少多少时间后这个矩形可以框住这n个点(严格)。
解析:
求出每个点运动到这个矩形内的时间的区间,求一个区间交。如果不存在或是一个点(说明蹭过去了),就说明不行。
区间求法:
- 对于内部的点,求出速度方向上x的时间和y的时间取一个min即可。
- 对于外部的点比较麻烦。对于点做矩形的四个边的接触的时间,不行就是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);
}