【POJ – 1066】Treasure Hunt【线段相交】

【POJ – 1066】Treasure Hunt【线段相交】

问题链接:https://vjudge.net/problem/POJ-1066

Solution:

一开始没注意到对中点的描述是”of the wall of the room being entered”,还一位是整面墙的中点,最后发现不是,那么就好办了,判断一下进入点到目标点隔了几个墙,也就是连线与多少个给出的线段相交,找到那个最少数量加1(最开始进入也需要)就好。枚举当然不能枚举边界上所有实数点,我们枚举端点,这样,对于端点所在的这面墙自然就不用考虑了,因为如果假设我们从端点一侧进入需要穿过端点所在墙,那么我们必然可以从端点另一边进入,使得不必穿过端点所在墙,而不改变穿过其它墙的个数。【另外,整个运算没有涉及到除法,不会出现二进制下无限小数导致的误差(如根号9),只可能会出现精度误差,不过这道题使用double的话精度也足够了,所以不必考虑误差】

#include <iostream>
#include <climits>
#include <vector>
#include <algorithm>

using namespace std;

struct Point {
    double x, y;
    Point operator - (const Point p) const {
        Point ret = {x - p.x, y - p.y};
        return ret;
    }
    double operator ^ (const Point p) const {
        return x * p.y - y * p.x;
    }
};
struct Seg {
    Point s, e;
};

const int LIM = 35;
Seg data[LIM];

bool atTwoSide(const Seg s, const Point a, const Point b) {
    Point v1 = s.e - s.s;
    Point v2 = a - s.s;
    Point v3 = b - s.s;
    return (v1 ^ v2) * (v1 ^ v3) < 0;
}

double maxi(double a, double b) {return a > b ? a : b;}
double mini(double a, double b) {return a < b ? a : b;}

bool onSegment(const Seg &s, const Point &a) {
    Point v1 = s.e - s.s;
    Point v2 = a - s.s;
    return v1 ^ v2 == 0;
}

int main(void) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lf%lf%lf%lf", &data[i].s.x, &data[i].s.y, &data[i].e.x, &data[i].e.y);
    }
    Point dest;
    scanf("%lf%lf", &dest.x, &dest.y);
    if (n == 0) {
        printf("Number of doors = 1\n");
        return 0;
    }
    int ans = INT_MAX;
    for (int i = 0; i < n; i++) {
        Point tmp = data[i].s;
        int tmpcnt = 0;
        for (int j = 0; j < n; j++) {
            if (!onSegment(data[j], tmp) && atTwoSide(data[j], tmp, dest))
                tmpcnt++;
            if (tmpcnt > ans) break;
        }
        if (tmpcnt < ans) ans = tmpcnt;
        tmp = data[i].e;
        tmpcnt = 0;
        for (int j = 0; j < n; j++) {
            if (!onSegment(data[j], tmp) && atTwoSide(data[j], tmp, dest))
                tmpcnt++;
            if (tmpcnt > ans) break;
        }
        if (tmpcnt < ans) ans = tmpcnt;
    }
    printf("Number of doors = %d\n", ans + 1);
    return 0;
}