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

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

Solution:

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

#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【注意题目的坑】

Solution:

#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【线段相交】

Solution:

#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【线段相交】

Solution:

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

#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最短路】

Solution:

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

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

#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;
};
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++) {
if (dist[nx] > dist[crt] + adj[crt][i].w) {
if (dist[nx] != INF) ds.erase(nx);
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++)
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;
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)};
}
}
}
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)};
}
}
#ifdef DBG
show();
#endif
dijsktra();
printf("%.2f\n", dist[size]);
}
return 0;
}


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

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

Solution:

#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【直线与线段相交】

Solution:

#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【还是叉积判三点旋向】

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【叉积判定三点旋向】

Solution:

#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];

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);
for (int i = 0; i < n; i++) {
scanf("%d%d", xs + i, xe + i);
}
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 - 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;
}