POJ 2653 Pick-up Sticks
这是一道基础的计算几何题，判断线段是否规范相交。
原题地址：http://poj.org/problem?id=2653
POJ 2653 相交的棍子（不知该怎么翻译标题）
在一个平面上扔棍子，这些棍子的粗细可以忽略不计，显然，之后扔的棍子可能压在之前扔的棍子的上面（规范相交）。现在给出扔的棍子的总条数，以及每条棍子的两个端点坐标，求出扔完所有棍子之后，没有被任何棍子压住的棍子的编号。
输入数据
会有多组数据。每组数据的第一行有一个整数 n, 表示这组数据有 n 条棍子。接下来 n 行，每行有 4 个数 x1 y1 x2 y2, 表示这条棍子扔到平面上之后的坐标。扔棍子的顺序与输入数据的顺序一样，先给出的棍子先被扔在平面上。如果遇到 n 为 0, 那么就结束程序。
输出数据
对于每组数据，输出一行。行首需要输出“Top sticks: ”（注意冒号后面有空格），然后接着输出最后没有被压住的棍子编号。编号以逗号分隔，逗号后面要有空格。编号输出完毕之后输出一个句号。棍子的编号要以升序排列。
样例输入
5 1 1 4 2 2 3 3 1 1 -2.0 8 4 1 4 8 2 3 3 6 -2.0 3 0 0 1 1 1 0 2 1 2 0 3 1 0
样例输出
Top sticks: 2, 4, 5. Top sticks: 1, 2, 3.
注意
数据量可能比较大，如果用 C++ 的话，最好不要用 cin 和 cout 控制输入输出，而使用 C 的 scanf 和 printf.
解题思路
弄一个链表，链表里保存没有被压住的棍子。读入第一条棍子后将其入链，读其余棍子的时候，每读一个，就和链表里的所有棍子判断相交，如果规范相交则让其出链。最后把读到的棍子入链。最后再对这些编号排序即可。
源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | #include <algorithm> #include <cstdlib> #include <cstdio> #include <vector> #include <list> using namespace std; #define eps 1e-8 #define inf 1e8 #define foreach(i,c) for (__typeof((c).begin()) \ i = (c).begin(); i != (c).end(); ++i) inline int sgn(double a) { if (a <-eps) return -1; if (a > eps) return 1; return 0; } inline int abs(int a) { return a < 0 ? -a : a; } struct point { double x, y; point() { } point(double a, double b) : x(a), y(b) { } point operator-(const point &p) const { return point(x - p.x, y - p.y); } point operator+(const point &p) const { return point(x + p.x, y + p.y); } }; inline double cross(const point &a, const point &b) { return a.x * b.y - b.x * a.y; } struct line { point a, b; size_t id; line() { } line(const point &u, const point &v) : a(u), b(v) { } bool operator<(const line &l) const { return id < l.id; } point vec() const { return b - a; } }; inline int relps(const point &p, const line &s) { return sgn(cross(p - s.a, s.vec())); } inline int relss(const line &sa, const line &sb) { int saa = relps(sa.a, sb); int sab = relps(sa.b, sb); int sba = relps(sb.a, sa); int sbb = relps(sb.b, sa); if (saa * sab == -1 && sba * sbb == -1) return 0; return 1; } list<line> lines; vector<line> buffer; int main(int argc, char *argv[]) { size_t n; while (scanf("%lu", &n)) { if (n == 0) break; lines.clear(); buffer.clear(); for (size_t i = 0; i < n; ++i) { line segment; segment.id = i; scanf("%lf%lf%lf%lf", &segment.a.x, &segment.a.y, &segment.b.x, &segment.b.y); foreach (it, lines) { if (!relss(*it, segment)) lines.erase(it--); } lines.push_back(segment); } foreach (it, lines) buffer.push_back(*it); sort(buffer.begin(), buffer.end()); printf("Top sticks: %lu", buffer[0].id + 1); for (vector<line>::iterator it = buffer.begin() + 1; it != buffer.end(); ++it) { printf(", %lu", it->id + 1); } printf(".\n"); } return EXIT_SUCCESS; } |
原创文章，转载请注明来源：http://euyuil.com/2410/poj-2653-pick-up-sticks/
不错呀，我想到的是用数组模拟…最后还得全部找一次…好像我的效率太低了-。-
什么意思啊？
没什么…蠢了一次而已。