Link

点击打开hdu题目链接

Mean

有一辆车要拐过一个拐角路口,给你两条路的宽度和车的长和宽,问你能不功能成功拐过路口。

Analyse

这道题是个人赛上的,经过长春区域赛打铁的教训,不会做就暴力啊!!!果真就又爆过去了,没有用三分。

就是假定车沿着右下角拐着走,枚举角度,然后判断路口左上角那个顶点与车身右边直线的距离,这样就转化成点到直线的距离,判断是否小于w即可。这样判出来是78ms。

正解是三分法,上面所说的哪个距离明显是一个凹函数,这样三分法求出最近距离,最后判断是否小于w即可。当然这次是首次做三分,要不然就不会上暴力了…

不用按照网上的方法推出最终的公式来,直接按照刘汝佳书上的模板,计算点到直线(向量)的距离即可。

暴力Code

#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-7;
struct Point {
    double x, y;
    Point():x(0), y(0){}
    Point(double x, double y):x(x), y(y){}
    Point operator - (Point & rhs) { return Point(x - rhs.x, y - rhs.y); }
    double length() { return hypot(x, y); }
};

double cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
double disToLine(Point P, Point A, Point B) {
    Point v1 = B - A, v2 = P - A;
    return fabs(cross(v1, v2)) / v1.length();
}

int main() {
    double x, y, l, w;
    while(~scanf("%lf%lf%lf%lf", &x, &y,&l, &w)) {
        if(w > x || w > y) {
            puts("no");
            continue;
        }
        Point t(y, x);
        double step = 0.0001, ed = acos(-1.0) / 2;
        bool ok = true;
        for(double i = step; i < ed; i += step) {
            Point a(cos(i)*l, 0), b(0, sin(i)*l);
            if(disToLine(t, a, b) < w) {
                ok = false;
                break;
            }
        }
        if(ok) puts("yes");
        else puts("no");
    }
    return 0;
}

三分法Code

#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-8;
struct Point {
    double x, y;
    Point():x(0), y(0){}
    Point(double x, double y):x(x), y(y){}
    Point operator - (Point & rhs) { return Point(x - rhs.x, y - rhs.y); }
    double length() { return hypot(x, y); }
};
double cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
double disToLine(Point P, Point A, Point B) {
    Point v1 = B - A, v2 = P - A;
    return fabs(cross(v1, v2)) / v1.length();
}

//-------------------------------------

double x, y, l, w;
Point t;

double dis(double i) {
    return disToLine(t, Point(cos(i)*l, 0), Point(0, sin(i)*l));
}

int main() {

    while(~scanf("%lf%lf%lf%lf", &x, &y,&l, &w)) {
        if(w > x || w > y) {
            puts("no");
            continue;
        }
        t = Point(y, x);
        double L = 0.0, R = acos(-1.0)/2;
        while(R-L > eps) {
            double mid1 = L + (R-L)/3;
            double mid2 = L + ((R-L)/3)*2;
            if(dis(mid1) < dis(mid2)) R = mid2;
            else L = mid1;
        }
        if(dis(L) < w) puts("no");
        else puts("yes");
    }
    return 0;
}

 

欢迎留言