题目

{% fold 点击显/隐题目 %}

题解

一开始没仔细读题,没有考虑中点,直接求了向各个方向相交最小值
(一般按照套路也只能这样算)

注意到中点后,推了一下,发现好像不需要刻意考虑中点
大概理由如下:
从任意一个位置到宝藏处,要通过的墙是确定的,不需要可以考虑墙的先后顺序
如果直接走过来不穿这个墙,就说明这个墙对我们毫无影响
如果直接走过来穿了这个墙,不管先穿后穿只打一个洞就行了(相当于通过了这一层)

因此直接跑就行了

最后记得记上边界墙
同时判断相交不考虑端点情况
特判 n==0

代码

{% fold 点击显/隐代码 %}```cpp Treasure Hunt https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include
#include
#include
#include
#include
using namespace std;

#define Log(format, ...) // printf(format, ##VA_ARGS)

/* 计算几何模板 */
const double eps = 1e-8;
const double INF = 9e50;
typedef complex Vector;
typedef Vector Point;
struct Segment {
Point a, b;
Segment() {}
Segment(Point _a, Point _b) : a(_a), b(_b) {}
Vector toVector() { return b - a; }
};

inline Point read_Point() {
double x, y;
scanf("%lf%lf", &x, &y);
return Point(x, y);
}
inline int sgn(const double &x) {
if (fabs(x) < eps)
return 0;
return x > 0 ? 1 : -1;
}
inline bool operator==(const Vector &vec1, const Vector &vec2) {
return sgn(vec1.real() - vec2.real()) == 0 &&
sgn(vec1.imag() - vec2.imag()) == 0;
}
inline bool operator!=(const Vector &vec1, const Vector &vec2) {
return !(vec1 == vec2);
}

inline int Cross(const Vector &a, const Vector &b) {
return a.real() * b.imag() - a.imag() * b.real();
}
inline int Dot(const Vector &a, const Vector &b) {
return a.real() * b.real() + a.imag() * b.imag();
}

inline double Distance(const Point &a, const Point &b) { return abs(a - b); }

inline int Point_Segment(const Vector &p, const Segment &L) {
return sgn(Cross(L.b - L.a, p - L.a));
}
inline int Segment_Segment(const Segment L1, const Segment L2) {
double a = L1.b.real() - L1.a.real();
double b = L2.b.real() - L2.a.real();
double c = L1.b.imag() - L1.a.imag();
double d = L2.b.imag() - L2.a.imag();
double f = a * d - b * c;

// 平行或重叠
if (sgn(f) == 0)
    return -1;

double g = L2.b.real() - L1.a.real();
double h = L2.b.imag() - L1.a.imag();
double t = (d * g - b * h) / f;
double s = (-c * g + a * h) / f;

// 在延长线上
if (t <= 0 || t >= 1 || s <= 0 || s >= 1)
    return 0;

// 线段相交
return 1;

}

const int maxn = 35;
int n;
Segment segments[maxn];

int calc(Segment L) {
int cnt = 0;
for (int i = 0; i < n; ++i)
cnt += (Segment_Segment(L, segments[i]) > 0);
return cnt;
}

int main() {
while (~scanf("%d", &n)) {
for (int i = 0; i < n; ++i) {
segments[i].a = read_Point();
segments[i].b = read_Point();
}
Point target = read_Point();

    int ans = 9999999;
    for (int i = 0; i < n; i++) {
        ans = min(ans, calc(Segment(target, segments[i].a)));
        ans = min(ans, calc(Segment(target, segments[i].b)));
    }
    if (n == 0)
        ans = 0;
    printf("Number of doors = %d\n", ans + 1);
}
return 0;

}

{% endfold %}