列表

详情


NC216009. InterestedinSkiing

描述

Kotori is interested in skiing. The skiing field is an infinite strip going along y-axis on the 2-dimensional plane where all points (x, y) in the field satisfies . When skiing, Kotori cannot move out of the field, which means that the absolute value of his x-coordinate should always be no more than m. There are also n segments on the ground which are the obstacles and Kotori cannot move across the obstacles either.

Kotori will start skiing from (you can regard this y-coordinate as a negative infinity) and moves towards the positive direction of the y-axis. Her vertical (parallel to the y-axis) speed is always v_y which cannot be changed, however she can control her horizontal (parallel to the x-axis) speed in the interval of . The time that Kotori changes her velocity can be neglected.

Your task is to help Kotori calculate the minimum value of that once she can safely ski through the skiing field without running into the obstacles.

输入描述

There is only one test case in each test file.

The first line of the input contains three positive integers n, m and v_y (, , ), indicating the number of obstacles, the half width of the skiing field and the vertical speed.

For the following n lines, the i-th line contains four integers x_1, y_1, x_2 and y_2 (, , or ) indicating the i-th obstacle which is a segment connecting point (x_1, y_1) and (x_2, y_2), both inclusive (that is to say, these two points are also parts of the obstacle and cannot be touched). It's guaranteed that no two obstacles intersect with each other.

输出描述

Output one line containing one number indicating the minimum value of . If it is impossible for Kotori to pass through the skiing field, output "-1" (without quotes) instead.

Your answer will be considered correct if and only if its absolute or relative error does not exceed .

示例1

输入:

3 2 1
-2 0 1 0
-1 4 2 4
0 1 0 3

输出:

1.000000000000000

示例2

输入:

2 1 2
-1 0 1 0
1 1 0 1

输出:

-1

示例3

输入:

2 3 7
-3 0 2 2
3 1 -2 17

输出:

1.866666666666666

示例4

输入:

1 100 1
-100 0 99 0

输出:

0.000000000000000

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++(clang++11) 解法, 执行用时: 8ms, 内存消耗: 400K, 提交时间: 2021-05-15 19:27:39

#include<bits/stdc++.h>
#define cha(p1,p2,p3) (det(p2-p1,p3-p1))
#define fi first 
#define se second
using namespace std;
typedef double db;
const db INF=1e20;
struct P{
    int x,y;
    P(int _x=0,int _y=0):x(_x),y(_y){}
    bool operator<(const P&a)const{return y<a.y;}
    P operator-(P p){return P(x-p.x,y-p.y);}
};
int det(P a,P b){
    return a.x*b.y-a.y*b.x;
}
int sign(int a){
    return a==0?0:a>0?1:-1;
}
const int maxn=105;
bool isSegInter(P p1,P p2,P q1,P q2){
    return sign(cha(p1,p2,q1))*sign(cha(p1,p2,q2))<0&&sign(cha(q1,q2,p1))*sign(cha(q1,q2,p2))<0;
}

db dp[maxn<<1];
int n,m,vy;
P p[maxn<<1];
pair<P,P>L[maxn<<1];

bool ok(P a,P b){
    for(int i=0;i<n;++i){
        if(isSegInter(a,b,L[i].fi,L[i].se))return 0;
    }
    return 1;
}
int main(){
    scanf("%d%d%d",&n,&m,&vy);
    for(int i=0;i<n;++i){
        scanf("%d%d",&p[i<<1].x,&p[i<<1].y);
        scanf("%d%d",&p[i<<1|1].x,&p[i<<1|1].y);
        L[i]={p[i<<1],p[i<<1|1]};
    }
    sort(p,p+2*n);
    for(int i=0;i<2*n;++i)dp[i]=INF;
    db ans=INF;
    for(int i=0;i<2*n;++i){
        if(p[i].x<=-m||p[i].x>=m)continue;//必须加 此时已经边界转移过去铁定无法满足
        if(ok(P(p[i].x,-10001),p[i]))dp[i]=0;//边界
        for(int j=0;j<i;++j){
            if(p[i].y==p[j].y)break;
            if(ok(p[i],p[j])){
                dp[i]=min(dp[i],max(dp[j],fabs(1.0*(p[i].x-p[j].x)/(p[i].y-p[j].y))));
            }

        }
        if(ok(P(p[i].x,10001),p[i]))ans=min(ans,dp[i]);//可以到终点
    }
    if(ok(P(0,-10001),P(0,10001)))ans=0;//考虑起点和终点的贡献
    if(ans>1e15)cout<<-1<<"\n";
    else printf("%.10f\n",ans*vy);
    return 0;
}

上一题