计算几何的基础题目。是时候刷刷计算几何了。
/* 2150 */
#include <cstdio>
#include <cstring>
#include <cstdlib> typedef struct {
int x, y;
} Point_t; typedef struct {
Point_t b, e;
int v;
} Pipe_t; #define MAXN 105 Point_t points[MAXN];
Pipe_t pipes[MAXN*]; int max(int a, int b) {
return a>b ? a:b;
} int min(int a, int b) {
return a<b ? a:b;
} int direction(Point_t p0, Point_t p1, Point_t p2) {
return (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y);
} bool onSegment(Point_t p0, Point_t p1, Point_t p2) {
if ( (min(p0.x,p1.x)<=p2.x && p2.x<=max(p0.x,p1.x)) && ((min(p0.y,p1.y)<=p2.y && p2.y<=max(p0.y,p1.y))) )
return true;
return false;
} bool intersect(Pipe_t x, Pipe_t y) {
if (x.v == y.v)
return false;
Point_t p1 = x.b, p2 = x.e, p3 = y.b, p4 = y.e;
int d1 = direction(p3, p4, p1);
int d2 = direction(p3, p4, p2);
int d3 = direction(p1, p2, p3);
int d4 = direction(p1, p2, p4);
if ( ((d1> && d2<) || (d1< && d2>)) && ((d3< && d4>) || (d3> && d4<)) )
return true;
else if (d1== && onSegment(p3, p4, p1))
return true;
else if (d2== && onSegment(p3, p4, p2))
return true;
else if (d3== && onSegment(p1, p2, p3))
return true;
else if (d4== && onSegment(p1, p2, p4))
return true;
else
return false;
} int main() {
int n, m;
int i, j, k;
bool flag; #ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif while (scanf("%d", &n) != EOF) {
m = ;
flag = true;
for (i=; i<n; ++i) {
scanf("%d", &k);
for (j=; j<k; ++j)
scanf("%d %d", &points[j].x, &points[j].y);
for (j=; j<k; ++j) {
pipes[m].b = points[j-];
pipes[m].e = points[j];
pipes[m].v = i;
++m;
}
}
for (i=; i<m; ++i) {
for (j=i+; j<m; ++j) {
if (intersect(pipes[i], pipes[j])) {
flag = false;
goto _output;
}
}
}
_output:
if (flag)
printf("No\n");
else
printf("Yes\n");
} return ;
}