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