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