【POJ-1696】Space Ant【Graham Scan + polar angle sorting】

【POJ-1696】Space Ant【Graham Scan + polar angle sorting】

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

Solution:

写的十分扎心的一题,改了好长时间,使用Graham Scan算法,求单个凸包复杂度\(O(nlogn)\),通过把丢弃的点重新利用再次求凸包的方法,最后将所有点遍历。

Graham Scan算法大体思路是首先找到最下方的点,之后以这个点为参照将所有点按照极角进行排序【实际上,由于不便于求解角度,我们使用判断三点围成矢量三角的旋转方向的方法来判断两个点那个点的极角更小,使用这种方法将不考虑极角的正负,所以即便我们选取的点不是最下方的点也会将所有的点从最下方的点开始排序,前提是,选作参照的点不能是四周都有点的,同时应当保证这个点在所求凸包上】,当两个点具有相同的极角时,我们按照距离从近到远进行排序。排好序后,我们首先把前三个点加入到栈中,接着从第四个点开始遍历,不断用下面这三个点判断旋向:

栈顶下面的一个元素→栈顶元素→新枚举的点

接着是第一个有变化的地方,通常我们求解凸包时,只在上面的旋向是逆时针的时候才保留栈顶元素,而这道题,为了走得距离最近,当三点共线的时候也保留栈顶元素,其余情况弹出栈顶,对应更新上面用到的两个栈中的点,使它们的含义与当前的栈的情况相符。另外一个不同的地方是,从栈顶丢掉的点现在我们不丢掉,而是存放到一个vector里,它们将用来求解下一次凸包。当我们求完一圈凸包后,我们将参照点置为当前栈顶元素,接着,在刚才抛弃的点集里重新进行极角排序,再次求解凸包,需要注意的是,这次就不能直接将前三个元素推到栈中了,而是直接接着已有的栈进行判断遍历每一个点,因为可能会遇到需要删除栈中点的情况,在下面的数据中,第一个n为14的就是例子。

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

const int LIM = 50 + 10;
struct Point {
    int x, y, id;
    Point operator - (const Point &p) const {
        Point ret = {x - p.x, y - p.y};
        return ret;
    }
    int operator ^ (const Point &p) const {
        return x * p.y - y * p.x;
    }
} ps[LIM];
int n;
Point bottom;
enum {CLOCK = -1, COL, CONTER};
int getOrientation(const Point &a, const Point &b, const Point &c) {
    Point v1 = b - a;
    Point v2 = c - a;
    int res = v1 ^ v2;
    if (res < 0) return CLOCK;
    else if (res == 0) return COL;
    else return CONTER;
}
int distSq(const Point &a, const Point &b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
bool cmp(const Point &a, const Point &b) {
    int o = getOrientation(bottom, a, b);
    if (o == COL)
        return distSq(a, bottom) <= distSq(b, bottom);
    return o == CONTER;
}

stack<Point> s;
void GramahScan() {
    if (n <= 3) {
        for (int i = 1; i <= n; i++)
            s.push(ps[i]);
        return;
    }
    bottom = ps[1];
    vector<Point> full, unduplicated, dup;
    full.push_back(ps[1]);
    /* Find the bottom point */
    for (int i = 2; i <= n; i++) {
        full.push_back(ps[i]);
        if (ps[i].y < bottom.y) bottom = ps[i];
    }
#ifdef DBG
    /* Show the bottom */
    printf("At %d: id = %d: %d, %d\n", __LINE__, bottom.id, bottom.x, bottom.y);
#endif
    /* polar angle sorting using bottom point */
    sort(full.begin(), full.end(), cmp);
#ifdef DBG
    /* Show the full after sort */
    printf("After sorting...\n");
    for (int i = 0; i < full.size(); i++)
        printf("At %d: id = %d: %d, %d\n", __LINE__, full[i].id, full[i].x, full[i].y);
#endif
    for (int i = 0; i < full.size(); i++) {
        unduplicated.push_back(full[i]);
    }
    Point top;
    Point nexttop;
    /* 最初插入三个 */
    s.push(unduplicated[0]);
    s.push(unduplicated[1]);
    s.push(unduplicated[2]);
    unduplicated.erase(unduplicated.begin());
    unduplicated.erase(unduplicated.begin());
    unduplicated.erase(unduplicated.begin());
    while (unduplicated.size() > 1) {
#ifdef DBG
        printf("__usize: %d__\n", unduplicated.size());
#endif
        for (int i = 0; i < unduplicated.size(); i++) {
            top = s.top();
            s.pop();
            nexttop = s.top();
            while (getOrientation(nexttop, top, unduplicated[i]) != CONTER) {
                s.pop();
                dup.push_back(top);
#ifdef DBG
                printf("Note, at %d, we remove %d\n", __LINE__, top.id);
                printf("Note, at %d, new top is %d\n", __LINE__, nexttop.id);
#endif
                top = nexttop;
                nexttop = s.top();
            }
            s.push(top);
            s.push(unduplicated[i]);
#ifdef DBG
            printf("Ok, at %d, we add %d\n", __LINE__, unduplicated[i].id);
#endif
        }
        full = dup;
#ifdef DBG
        printf("At %d - full size: %d\n", __LINE__, full.size());
#endif
        unduplicated.clear();
        dup.clear();
        bottom = s.top();
#ifdef DBG
        printf("At %d - bottom id - %d: %d, %d\n", __LINE__, bottom.id, bottom.x, bottom.y);
#endif
        sort(full.begin(), full.end(), cmp);
#ifdef DBG
        /* Show the full after sort */
        printf("After sorting...\n");
        for (int i = 0; i < full.size(); i++)
            printf("At %d: id = %d: %d, %d\n", __LINE__, full[i].id, full[i].x, full[i].y);
#endif
        for (int i = 0; i < full.size(); i++) {
            unduplicated.push_back(full[i]);
        }
#ifdef DBG
        printf("At %d: dup size = %d\n", __LINE__, dup.size());
#endif
    }
    if (unduplicated.size()) s.push(unduplicated[0]);
}

void showAns() {
    Point crt = s.top();
    s.pop();
    if (!s.empty()) showAns();
    printf(" %d", crt.id);
}

int main(void) {
    int m;
    scanf("%d", &m);
    while (m--) {
        while (!s.empty()) s.pop();
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d%d", &ps[i].id, &ps[i].x, &ps[i].y);
        }
#ifdef DBG
        printf("Show all\n");
        for (int i = 1; i <= n; i++)
            printf("At %d: id = %d: %d, %d\n", __LINE__, ps[i].id, ps[i].x, ps[i].y);
#endif
        GramahScan();
        printf("%d", s.size());
        showAns();
        putchar('\n');
    }
    return 0;
}

数据:

3
14
1 	55 	24 
2 	86 	18 
3 	49 	39 
4 	62 	5 
5 	72 	84 
6 	69 	49 
7 	72 	99 
8 	71 	34 
9 	57 	37 
10 	6 	48 
11 	92 	43 
12 	98 	4 
13 	80 	69 
14 	33 	88 
28
1 	47 	25 
2 	47 	56 
3 	7 	44 
4 	98 	15 
5 	14 	94 
6 	29 	5 
7 	90 	94 
8 	90 	20 
9 	34 	30 
10 	14 	39 
11 	77 	56 
12 	92 	71 
13 	26 	59 
14 	7 	33 
15 	98 	8 
16 	99 	65 
17 	3 	57 
18 	89 	11 
19 	24 	94 
20 	26 	48 
21 	63 	8 
22 	64 	70 
23 	24 	46 
24 	34 	51 
25 	100 	31 
26 	82 	22 
27 	60 	60 
28 	55 	59 
12
1 	25 	28 
2 	56 	16 
3 	93 	41 
4 	18 	5 
5 	46 	38 
6 	19 	39 
7 	7 	64 
8 	12 	92 
9 	37 	69 
10 	74 	46 
11 	19 	71 
12 	87 	63 

 

【POJ-1410】Intersection【注意题目的坑】

【POJ-1410】Intersection【注意题目的坑】

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

Solution:

问题十分简单,如果线段与矩形有:相交、相切、包含于,这三者关系之一的话,就输出T,反之输出F,那么思路就是,首先判断一下端点在不在矩形内部,如果在则必然是T,如果不在则可能是F也可能是端点不在矩形内的相交,对于端点不在矩形内的相交,只要和矩形的两条对角线判断一下相交就好了。

关键的难点是,需要注意到”The terms top left and bottom right do not imply any ordering of coordinates.”,意思就是,输入比较皮,输入的左上角坐标不一定是左上角,右下角坐标也不一定是右下角,需要手动调整一下正确的左上角和右下角。

#include <iostream>

using namespace std;

struct Point {
    int x, y;
    Point operator - (Point &p) {
        Point retv = {x - p.x, y - p.y};
        return retv;
    }
    // cross product
    int operator ^ (Point &v) {
        return x * v.y - y * v.x;
    }
};

inline int maxi(int a, int b) {return a > b ? a : b;}
inline int mini(int a, int b) {return a < b ? a : b;}
inline void swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}

enum {CLOCK = -1, COL, COUNTER};
int getOrientation(Point &a, Point &b, Point &c) {
    Point v1 = b - a, v2 = c - a;
    int ans = v1 ^ v2;
    if (ans < 0) return CLOCK;
    else if (ans == 0) return COL;
    return COUNTER;
}
bool onSegment(Point &s, Point &e, Point &p) {
    return p.x >= mini(s.x, e.x) && p.x <= maxi(s.x, e.x)
        && p.y >= mini(s.y, e.y) && p.y <= maxi(s.y, e.y);
}
bool isIntersect(Point &s1, Point &e1, Point &s2, Point &e2) {
    int o1 = getOrientation(s1, s2, e1);
    int o2 = getOrientation(s1, e2, e1);
    int o3 = getOrientation(s2, s1, e2);
    int o4 = getOrientation(s2, e1, e2);
    if (o1 != o2 && o3 != o4) return true;
    if (!o1 && !o2
        && mini(s1.x, e1.x) <= mini(s2.x, e2.x)
        && maxi(s1.x, e1.x) >= maxi(s2.x, e2.x)) return true;
    return false;
}

bool inArea(Point &p, Point &lt, Point &rb) {
    return p.x >= lt.x && p.x <= rb.x
        && p.y >= rb.y && p.y <= lt.y;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    Point s, e, lt, rb;
    while (n--) {
        cin >> s.x >> s.y >> e.x >> e.y >> lt.x >> lt.y >> rb.x >> rb.y;
        if (lt.x > rb.x) swap(lt.x, rb.x);
        if (lt.y < rb.y) swap(lt.y, rb.y);
        if (inArea(s, lt, rb) || inArea(e, lt, rb)) {
            cout << "T\n";
            continue;
        }
        Point lb = {lt.x, rb.y}, rt = {rb.x, lt.y};
        if (isIntersect(s, e, lt, rb) || isIntersect(s, e, lb, rt)) {
            cout << "T\n";
            continue;
        }
        cout << "F\n";
    }
    return 0;
}

 

【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;
}

 

【HDU-1147】Pick-up sticks【线段相交】

【HDU-1147】Pick-up sticks【线段相交】

问题链接:https://vjudge.net/problem/HDU-1147

Solution:

这道题的时间限制十分严格,一开始手动实现小顶堆+扫描线,一直TLE:

#include <iostream>
#include <set>
#include <map>
#include <vector>

// 扫描线版本,TLE。

using namespace std;

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

struct Point {
    double x, y;
    int id;
    bool operator < (const Point &p) const {
        return x < p.x;
    }
    Point operator - (const Point &p) const {
        Point ret = {x - p.x, y - p.y};
        return ret;
    }
    double operator ^ (const Point &v) const {
        return x * v.y - y * v.x;
    }
};

const int LIM = 1e5 + 10;
vector<Point> ps;
inline void swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}

struct Cmp {
    bool operator()(int a, int b) {
        return ps[a].x < ps[b].x;
    }
};

class MinHeap {
private:
    int heap_pos;
    int data[LIM];
    int cap;
    Cmp cmp;
public:
    MinHeap() : cap(LIM), heap_pos(1) {}
    int extractMin();
    bool doInsert(int key);
    void minHeapify(int idx);
    int size();
};

int MinHeap::extractMin() {
    if (heap_pos == 1) {
        return INT_MAX;
    } else if (heap_pos == 2) {
        heap_pos--;
        return data[1];
    } else {
        int ret = data[1];
        heap_pos--;
        data[1] = data[heap_pos];
        minHeapify(1);
        return ret;
    }
}

bool MinHeap::doInsert(int key) {
    if (heap_pos == cap)
        return false;
    data[heap_pos] = key;
    for (int i = heap_pos; i > 1 && cmp(data[i], data[i >> 1]); i >>= 1)
        swap(data[i >> 1], data[i]);
    heap_pos++;
    return true;
}

void MinHeap::minHeapify(int idx) {
    int i = idx;
    if ((idx << 1) < heap_pos && cmp(data[idx << 1], data[i]))
        i = idx << 1;
    if ((idx << 1 | 1) < heap_pos && cmp(data[idx << 1 | 1], data[i]))
        i = idx << 1 | 1;
    if (i != idx) {
        swap(data[i], data[idx]);
        minHeapify(i);
    }
}

int MinHeap::size() {
    return heap_pos - 1;
}

enum {CLOCK, CONTER, COL};
int getOrientation(Point a, Point b, Point c) {
    Point v1 = b - a;
    Point v2 = c - a;
    double cross = v1 ^ v2;
    if (cross < 0) return CLOCK;
    else if (cross == 0) return COL;
    else return CONTER;
}

bool onSegment(Point s, Point e, Point p) {
    return p.x >= mini(s.x, e.x) && p.x <= maxi(s.x, e.x)
        && p.y >= mini(s.y, e.y) && p.y <= maxi(s.y, e.y);
}

bool isIntersect(Point s1, Point e1, Point s2, Point e2) {
    int oa = getOrientation(s1, s2, e1);
    int ob = getOrientation(s1, e2, e1);
    int oc = getOrientation(s2, s1, e2);
    int od = getOrientation(s2, e1, e2);
    if (oa != ob && oc != od) return true;
    if (oa == COL && onSegment(s1, e1, e2)) return true;
    if (ob == COL && onSegment(s1, e1, s2)) return true;
    if (oc == COL && onSegment(s2, e2, e1)) return true;
    if (od == COL && onSegment(s2, e2, s1)) return true;
    return false;
}

int main(void) {
    int n;
    Point s, e, crt;
    while (~scanf("%d", &n) && n) {
        ps.clear();
        MinHeap mh;
        for (int i = 0; i < n; i++) {
            scanf("%lf%lf%lf%lf", &s.x, &s.y, &e.x, &e.y);
            s.id = e.id = i + 1;
            ps.push_back(s);
            ps.push_back(e);
            mh.doInsert(i * 2);
            mh.doInsert(i * 2 + 1);
        }
        set<int> active;
        set<int> ans;
        vector<int> toDel;
        while (mh.size()) {
            crt = ps[mh.extractMin()];
            if (!toDel.empty() && crt.x != ps[toDel[0]].x) {
                for (int x : toDel) {
                    active.erase(x);
                }
                toDel.clear();
            }
            if (active.count(crt.id)) toDel.push_back(crt.id);
            else active.insert(crt.id);
            for (int x : active) {
                for (int y : active) {
                    if (x > y) continue;
                    else if (x == y) {
                        ans.insert(x);
                        continue;
                    }
                    if (isIntersect(ps[(x - 1) * 2], ps[(x - 1) * 2 + 1],
                        ps[(y - 1) * 2], ps[(y - 1) * 2 + 1])) {
                        int over = maxi(x, y);
                        int suf = mini(x, y);
                        if (ans.count(suf)) ans.erase(suf);
                        ans.insert(over);
                    } else {
                        ans.insert(x);
                        ans.insert(y);
                    }
                }
            }
        }
        printf("Top sticks: ");
        set<int>::iterator ite;
        int i;
        for (i = 0, ite = ans.begin(); ite != ans.end(); ite++, i++) {
            if (i) printf(", ");
            printf("%d", *ite);
        }
        printf(".\n");
    }
    return 0;
}

扫描线复杂度应该是\(O(nlogn)\),最差\(O(n^2)\)的,但是需要维护一个激活集合,这道题时间卡得紧,需要一个更符合这道题的解法。

这道题的解法其实也挺简单,表面上我们是用了一个\(O(n^2)\)的算法,但是实际上,最优能够降到\(O(n)\),可能这就是用这种方法能够AC的原因,简单说一下,其实就是一个筛选法,另开一个数组,筛选掉的直接扔掉,降低里层循环规模,维护一个紧密型线性存储,充分利用CPU的Cache,速度会有明显提升。

#include <iostream>

using namespace std;

struct Seg {
    double x1, y1, x2, y2;
    int id;
};

inline double crossPro(double x1, double y1, double x2, double y2) {
    // printf("(%f, %f) ^ (%f, %f)\n", x1, y1, x2, y2);
    return x1 * y2 - y1 * x2;
}

const int LIM = 1e5 + 10;
Seg ps[LIM];
Seg ans[LIM];
int gblcnt;

inline double maxi(double a, double b) {return a > b ? a : b;}
inline double mini(double a, double b) {return a < b ? a : b;}
inline bool onSegment(Seg s, double px, double py) {
    return maxi(s.x1, s.x2) >= px && px >= mini(s.x1, s.x2)
        && maxi(s.y1, s.y2) >= py && py >= mini(s.y1, s.y2);
}


inline int sgn(int x) {
    if (x < 0) return -1;
    else if (x == 0) return 0;
    return 1;
}
bool isIntersect(Seg s1, Seg s2) {
    double oa = crossPro(s1.x2 - s1.x1, s1.y2 - s1.y1, s2.x1 - s1.x1, s2.y1 - s1.y1);
    double ob = crossPro(s1.x2 - s1.x1, s1.y2 - s1.y1, s2.x2 - s1.x1, s2.y2 - s1.y1);
    double oc = crossPro(s2.x2 - s2.x1, s2.y2 - s2.y1, s1.x1 - s2.x1, s1.y1 - s2.y1);
    double od = crossPro(s2.x2 - s2.x1, s2.y2 - s2.y1, s1.x2 - s2.x1, s1.y2 - s2.y1);
    // cout << oa << ob << oc << od << endl;
    if (sgn(oa) != sgn(ob) && sgn(oc) != sgn(od)) return true;
    if (!oa && onSegment(s1, s2.x2, s2.y2)) return true;
    if (!ob && onSegment(s1, s2.x1, s2.y1)) return true;
    if (!oc && onSegment(s2, s1.x2, s1.y2)) return true;
    if (!od && onSegment(s2, s1.x1, s1.y1)) return true;
    return oa * ob < 0 && oc * od < 0;
}

int main(void) {
    int n;
    while (~scanf("%d", &n) && n) {
        gblcnt = n;
        for (int i = 0; i < n; i++) {
            scanf("%lf%lf%lf%lf", &ps[i].x1, &ps[i].y1, &ps[i].x2, &ps[i].y2);
            ps[i].id = i + 1;
            ans[i] = ps[i];
        }
        for (int i = n - 1; i >= 0; i--) {
            int tmpcnt = 0;
            for (int j = 0; j < gblcnt; j++) {
                if (ps[i].id <= ans[j].id || !isIntersect(ps[i], ans[j])) {
                    ans[tmpcnt++] = ans[j];
                }
            }
            gblcnt = tmpcnt;
        }
        printf("Top sticks: ");
        for (int i = 0; i < gblcnt; i++)
            if (i) printf(", %d", ans[i].id);
            else printf("%d", ans[i].id);
        printf(".\n");
    }
    return 0;
}

 

【POJ-1556】The Doors【线段相交、Dijkstra最短路】

【POJ-1556】The Doors【线段相交、Dijkstra最短路】

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

Solution:

我们需要建一个带权DAG图,权重是两点间距离,用双精度浮点数记录,点集是由所有输入的点以及(0, 5), (10, 5)两个点组成的集合,两点连接有边的必要条件是:1.起点必须严格在终点的左边,2.从起点到终点的连线不能被墙遮挡。现在需要考虑如何确认没有遮挡,其实很简单,就是线段相交。根据题目的数据输入,我们确定一个处理顺序。

  1. 新建一个空点集,新建一个空邻接表,一个线段集【用来装墙】。
  2. 将点集中加入初始点(0, 5)。
  3. 循环读取4个新的点:
    1. 对于每个读取的点,判断当前点集中的两个横坐标不同的点与新的点连线是否与线段集中横坐标位于两个点之间的线段有相交:
      1. 如果有则遍历另外的两个点。
      2. 如果没有则在邻接表中插入这一条新的边,并且权重是两点距离。
    2. 将新增加的三段墙加入到线段集中。
  4. 将点集中最后加入的四个点在邻接表上与结束点(10, 5)相连。
  5. 使用dijkstra算法找到从初始点(0, 5)到结束点(10, 5)的最短路。

点集、邻接表、线段集都使用vector来实现。假设总共有V个点,则遍历可以连接的点的复杂度是\(O(V^2)\),对于每种连线方式,用来判断与线段相交的复杂度是\(O(E)\),其中E表示墙的数量,显然\(E = \frac{V – 2}{4} \times 3\),所以这个的复杂度也写作\(O(V)\),插入操作的是\(O(1)\)的,我们并不关注,所以第三步的时间复杂度是\(O(V^3)\),之后Dijkstra算法通过使用set实现,其时间复杂度为\(O(E_2logV)\),其中\(E_2\)表示邻接表中边的数量,最差情况下,有:

\(E_2 = V \times (V – 1) – 4 \times 3 \times (V – 2)  = V^2 – 13V + 24\),

也就是说,\(O(E_2logV)\)大致为\(O(V^2logV)\),所以此解法的总体复杂度是\(O(V^2logV) + O(V^3) = O(V^3)\)。

#include <iostream>
#include <set>
#include <vector>
#include <cmath>
// #define DBG

using namespace std;

const int LIM = 1000;
const double INF = 1000000;
struct Node {
    int idx;
    double w;
};
struct Point {
    double x, y;
    int id;
    Point operator - (const Point p) const {
        Point ret = {x - p.x, y - p.y};
        return ret;
    }
    double operator ^ (const Point p) {
        return x * p.y - y * p.x;
    }
};
struct Seg {
    Point s, e;
};
vector<Node> adj[LIM];
double dist[LIM];
int n, size;
struct cmp {
    bool operator()(const int a, const int b) {
        if (dist[a] != dist[b]) return dist[a] < dist[b];
        return a < b;
    }
};

void dijsktra() {
    // init
    for (int i = 0; i <= size; i++) dist[i] = INF;
    dist[0] = 0;
    set<int, cmp> ds;
    ds.insert(0);
    int crt, nx;
    while (!ds.empty()) {
        crt = *ds.begin();
        ds.erase(crt);
        if (crt == size) return;
#ifdef DBG
        printf("%d: dis=%f\n", crt, dist[crt]);
#endif
        for (int i = 0; i < adj[crt].size(); i++) {
            nx = adj[crt][i].idx;
            if (dist[nx] > dist[crt] + adj[crt][i].w) {
                if (dist[nx] != INF) ds.erase(nx);
                dist[nx] = dist[crt] + adj[crt][i].w;
                ds.insert(nx);
            }
        }
    }
}

double getDist(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

enum {CONTER = -1, COL, CLOCK};
int getOrientation(Point &a, Point &b, Point &c) {
    Point v1 = b - a;
    Point v2 = c - a;
    double tmp = v1 ^ v2;
    if (tmp < 0) return CONTER;
    else if (tmp > 0) return CLOCK;
    else return COL;
}

inline double mini(double a, double b) {return a < b ? a : b;}
inline double maxi(double a, double b) {return a > b ? a : b;}
bool onSegment(Point s, Point e, Point p) {
    return p.x >= mini(s.x, e.x) && p.x <= maxi(s.x, e.x)
        && p.y >= mini(s.y, e.y) && p.y <= maxi(s.y, e.y);
}

bool isIntersect(Point a, Point b, Point c, Point d) {
    int oa = getOrientation(a, c, b);
    int ob = getOrientation(a, d, b);
    int oc = getOrientation(c, a, d);
    int od = getOrientation(c, b, d);
    if (oa != ob && oc != od) return true;
    if (!oa && onSegment(a, b, d)) return true;
    if (!ob && onSegment(a, b, c)) return true;
    if (!oc && onSegment(c, d, b)) return true;
    if (!od && onSegment(c, d, a)) return true;
    return false;
}

#ifdef DBG
void show() {
    for (int i = 0; i < size; i++) {
        printf("%d:\n", i);
        for (int j = 0; j < adj[i].size(); j++)
            printf("\t%d", adj[i][j].idx);
        putchar('\n');
    }
}
#endif

int main(void) {
    double y[4];
    while (~scanf("%d", &n) && n != -1) {
        // To store the barriers
        vector<Seg> barset;
        vector<Seg>::iterator ite;
        // To store the current points
        vector<Point> pset;
        vector<Point>::iterator pite;
        // init the adjacent table
        for (int i = 0; i < LIM; i++) adj[i].clear();
        // put initial point (0, 5) into pset
        Point crt = {0, 5, 0};
        pset.push_back(crt);
        size = 1;
        for (int i = 0; i < n; i++, size = pset.size()) {
            scanf("%lf%lf%lf%lf%lf", &crt.x, y, y + 1, y + 2, y + 3);
            // iterate all possible way to build a path between the point in
            // pset, and the point which is new.
            for (pite = pset.begin(); pite != pset.end(); pite++) {
                for (int i = 0; i < 4; i++) {
                    crt.y = y[i];
                    bool flag = true;
                    for (ite = barset.begin(); ite != barset.end(); ite++) {
                        if ((*ite).s.x <= (*pite).x) continue;
                        if (isIntersect(*pite, crt, (*ite).s, (*ite).e)) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) {
                        Node tmp = {size + i, getDist((*pite).x, (*pite).y, crt.x, crt.y)};
                        adj[(*pite).id].push_back(tmp);
                    }
                }
            }
            crt.id = size, crt.y = y[0];
            pset.push_back(crt);
            crt.id = size + 1, crt.y = y[1];
            pset.push_back(crt);
            crt.id = size + 2, crt.y = y[2];
            pset.push_back(crt);
            crt.id = size + 3, crt.y = y[3];
            pset.push_back(crt);
            Seg tmp = {{crt.x, 0}, {crt.x, y[0]}};
            barset.push_back(tmp);
            tmp.s.y = y[1], tmp.e.y = y[2];
            barset.push_back(tmp);
            tmp.s.y = y[3], tmp.e.y = 10;
            barset.push_back(tmp);
        }
        crt.x = 10, crt.y = 5, crt.id = size;
        for (pite = pset.begin(); pite != pset.end(); pite++) {
            bool flag = true;
            for (ite = barset.begin(); ite != barset.end(); ite++) {
                if ((*ite).s.x <= (*pite).x) continue;
                if (isIntersect(*pite, crt, (*ite).s, (*ite).e)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                Node tmp = {crt.id, getDist((*pite).x, (*pite).y, crt.x, crt.y)};
                adj[(*pite).id].push_back(tmp);
            }
        }
#ifdef DBG
        show();
#endif
        dijsktra();
        printf("%.2f\n", dist[size]);
    }
    return 0;
}

 

【POJ-1269】Intersecting Lines【直线位置判断】

【POJ-1269】Intersecting Lines【直线位置判断】

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

Solution:

直线判断比线段判断简单,不过与线段判断不同的是,对于直线来说,平行是最好判断的,判断两个方向向量叉积是否为0就可以判断平行;至于判断共线,从两条直线上各取两点,首先固定选取一条直线上的这两个点,之后在另一条直线上分别取两点分别与刚才取的两点求一下三点的旋转方向,即通过叉积,之后只要确认两组三个点分别都是共线的,就可以确认两条直线共线。剩下的都是相交。

求交点直接使用解析几何的办法就好了,如果使用斜率需要讨论斜率是否存在的情况。

#include <iostream>

using namespace std;

struct Point {
    int x, y;
    Point operator - (Point b) {
        Point ret = {x - b.x, y - b.y};
        return ret;
    }
    bool operator == (const Point &p) {return x == p.x && y == p.y;}
    int cross(Point v) {
        return x * v.y - y * v.x;
    }
};
inline int maxi(int a, int b) {return a > b ? a : b;}
inline int mini(int a, int b) {return a < b ? a : b;}
enum {COUNT, CLOCK, COL};
int getOrientation(Point a, Point b, Point c) {
    Point vab = b - a;      /* The vector of a -> b */
    Point vac = c - a;      /* The vector of a -> c */
    int crossPro = vab.cross(vac);
    if (crossPro < 0) return CLOCK;
    if (crossPro > 0) return COUNT;
    return COL;
}

enum {POINT, NONE, LINE};
int isIntersect(Point ps1, Point pe1, Point ps2, Point pe2) {
    int oa = getOrientation(ps1, ps2, pe1);
    int ob = getOrientation(ps1, pe2, pe1);
    if (oa == COL && ob == COL) return LINE;
    Point v = pe1 - ps1;
    Point v2 = pe2 - ps2;
    if (!v.cross(v2)) return NONE;
    return POINT;
}
double ans[2];
void setAns(const Point &p) {
    ans[0] = p.x;
    ans[1] = p.y;
}
void getInterPoint(Point ps1, Point pe1, Point ps2, Point pe2) {
    if (ps1 == ps2 || ps1 == pe2) setAns(ps1);
    if (pe1 == ps2 || pe1 == pe2) setAns(pe1);
    double k1 = (pe1.y - ps1.y) * 1.0 / (pe1.x - ps1.x);
    double b1 = ps1.y - ps1.x * k1;
    double k2 = (pe2.y - ps2.y) * 1.0 / (pe2.x - ps2.x);
    double b2 = ps2.y - ps2.x * k2;
    if (ps1.x == pe1.x) {
        ans[0] = ps1.x;
        ans[1] = k2 * ans[0] + b2;
    } else if (ps2.x == pe2.x) {
        ans[0] = ps2.x;
        ans[1] = k1 * ans[0] + b1;
    } else {
        ans[0] = (b2 - b1) / (k1 - k2);
        ans[1] = k1 * ans[0] + b1;
    }
}

int main(void) {
    int n;
    Point ps1, pe1, ps2, pe2;
    while (~scanf("%d", &n)) {
        printf("INTERSECTING LINES OUTPUT\n");
        while (n--) {
            scanf("%d%d%d%d%d%d%d%d", &ps1.x, &ps1.y, &pe1.x, &pe1.y,
                &ps2.x, &ps2.y, &pe2.x, &pe2.y);
            if (ps1 == pe1 || ps2 == pe2) {
                printf("NONE\n");
                continue;
            }
            int state = isIntersect(ps1, pe1, ps2, pe2);
            if (state == LINE) printf("LINE\n");
            else if (state == NONE) printf("NONE\n");
            else {
                getInterPoint(ps1, pe1, ps2, pe2);
                printf("POINT %.2f %.2f\n", ans[0], ans[1]);
            }
        }
        printf("END OF OUTPUT\n");
    }
    return 0;
}

 

【POJ-3304】Segments【直线与线段相交】

【POJ-3304】Segments【直线与线段相交】

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

Solution:

题目问是否存在至少一条直线使得所有线段在该直线上的投影能够相交在至少一点上,如果我们取该直线这样的一个点,做该直线的垂线,必然有该直线穿过所有线段,同样的我们也能够发现,如果我们可以找到一条过所有线段的直线,那么我们对该直线做的任意垂线都满足题意,那么我们只要找到这样一条直线就好。

点的坐标是实数,实数是不可数集,我们显然无法枚举空间内的所有直线。我们需要一个更加“极端”的方法,如果存在这样的直线,我们设想所有这样的直线构成一个集合,那么这个集合中极端位置的直线应当满足什么条件,显然,极端直线会通过至少2个已知线段的端点,那么我们可以枚举所有端点构成的直线来判断就可以了。需要注意,可能存在多个相同的端点,所以如果两个端点是相同的,那么是无法拉出一条直线的,需要在枚举时跳过这种情况。

由于判断的是直线与线段相交,我们的判定方法可以比判断线段与线段相交的时候简化,只需要判断直线上两点与线段两点构成的两个三角形的旋转方向【顺时针/逆时针/共线】就好。

#include <iostream>
#include <cmath>
// #define DBG
using namespace std;

typedef long double LD;
const int LIM = 100 + 10;
const LD EPS = 1e-8;
struct Point {
    LD x, y;
    LD cross(const Point &p) const {
        return x * p.y - y * p.x;
    }
};
Point ps[LIM * 2];
int t, n;
inline LD dist(const Point &a, const Point &b) {
    return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}
bool isAns(const Point &a, const Point &b) {
    Point tmp = {b.x - a.x, b.y - a.y};
    for (int i = 0; i < n * 2; i += 2) {
        Point ta = {ps[i].x - a.x, ps[i].y - a.y};
        Point tb = {ps[i + 1].x - a.x, ps[i + 1].y - a.y};
        if (tmp.cross(ta) * tmp.cross(tb) > EPS)
            return false;
    }
    return true;
}

int main(void) {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        int size = n * 2;
        for (int i = 0; i < size; i += 2)
            scanf("%Lf%Lf%Lf%Lf", &ps[i].x, &ps[i].y, &ps[i + 1].x, &ps[i + 1].y);
        bool flag = true;
        for (int i = 0; flag && i < size; i++) {
            for (int j = i + 1; flag && j < size; j++) {
                if (dist(ps[i], ps[j]) < EPS) continue;
                if (isAns(ps[i], ps[j]) || isAns(ps[j], ps[i]))
                    flag = false;
            }
        }
        if (flag) printf("No!\n");
        else printf("Yes!\n");
    }
    return 0;
}

 

【POJ-2398】Toy Storage【还是叉积判三点旋向】

【POJ-2398】Toy Storage【还是叉积判三点旋向】

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

Solution:

【POJ-2318】TOYS【叉积判定三点旋向】处理方法完全相同,把那个结果的数组再重新用另外一个数组当做桶来处理一下,就可以了。需要注意的是,这道题给出的分隔板不再是从左到右顺序给出的,需要预先排序。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int LIM = 1000 + 10;
struct node {
    int xs, xe;
    bool operator < (const node &n) const {
        return xs < n.xs;
    }
};
int ans[LIM];
node x[LIM];
int cnt[LIM];

int cross(int ax, int ay, int bx, int by) {
    int tmp = ax * by - bx * ay;
    if (tmp == 0) return 0;
    else if (tmp < 0) return -1;
    else return 1;
}

int main(void) {
    int n, m, x1, y1, x2, y2, a, b;
    for (int k = 0; ~scanf("%d", &n) && n; k++) {
        printf("Box\n");
        memset(cnt, 0, sizeof cnt);
        memset(ans, 0, sizeof ans);
        scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &x[i].xs, &x[i].xe);
        }
        sort(x, x + n);
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &a, &b);
            int l = 0, r = n;
            while (l < r) {
                int mid = (l + r) >> 1;
                int flag = cross(a - x[mid].xe, b - y2, x[mid].xs - x[mid].xe, y1 - y2);
                if (flag < 0) r = mid;
                else if (flag > 0) l = mid + 1;
            }
            cnt[l]++;
        }
        for (int i = 0; i <= n; i++) ans[cnt[i]]++;
        for (int i = 1; i <= m; i++)
            if (ans[i]) printf("%d: %d\n", i, ans[i]);
    }
    return 0;
}

 

【POJ-2318】TOYS【叉积判定三点旋向】

【POJ-2318】TOYS【叉积判定三点旋向】

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

Solution:

使用叉积能够判断三个点是顺时针(clockwise)还是逆时针(counterclockwise),之后用二分搜索,注意到按照下面程序的方法,点一定是最后趋向的那个值所在线段的左边。

【注:为什么手动实现Fast I/O的read函数会TLE。。】

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int LIM = 5000 + 10;
int ans[LIM];
int xs[LIM], xe[LIM];
int cnt[LIM];

void read(int &x) {
    char ch = getchar();
    x = 0;
  for (; ch < '0' || ch > '9'; ch = getchar());
  for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}

int cross(int ax, int ay, int bx, int by) {
    int tmp = ax * by - bx * ay;
    if (tmp == 0) return 0;
    else if (tmp < 0) return -1;
    else return 1;
}

int main(void) {
    int n, m, x1, y1, x2, y2, a, b;
    for (int k = 0; ~scanf("%d", &n) && n; k++) {
        if (k) putchar('\n');
        memset(cnt, 0, sizeof cnt);
        scanf("%d%d%d%d%d", &m, &x1, &y1, &x2, &y2);
        // read(m);
        // read(x1);
        // read(y1);
        // read(x2);
        // read(y2);
        for (int i = 0; i < n; i++) {
            // read(xs[i]);
            // read(xe[i]);
            scanf("%d%d", xs + i, xe + i);
        }
        for (int i = 0; i < m; i++) {
            // read(a);
            // read(b);
            scanf("%d%d", &a, &b);
            int l = 0, r = n;
            while (l < r) {
                int mid = (l + r) >> 1;
                int flag = cross(a - xe[mid], b - y2, xs[mid] - xe[mid], y1 - y2);
                if (flag < 0) r = mid;
                else if (flag > 0) l = mid + 1;
            }
            cnt[l]++;
        }
        for (int i = 0; i <= n; i++) printf("%d: %d\n", i, cnt[i]);
    }
    return 0;
}