一道非常"简单"的计算几何题。。。
题意：给你两个三角形和一个四边形，问你能否用这两个三角形拼成这个四边形
首先。。。四边形可能是凹四边形。。。需要判断一下。。。这个比较简单直接分成两部分即可。。。
然后。。。四边形可能会退化成三角形。。。那就需要两个三角形拼起来的时候某两个角之和为180°
最后暴力一下如何划分四边形即可。。。
写的真是开心，还好一遍A了QAQ
/**************************************************************
Problem: 2494
User: rausen
Language: C++
Result: Accepted
Time:8 ms
Memory:820 kb
****************************************************************/ #include <cstdio>
#include <cmath>
#include <algorithm> using namespace std;
typedef double lf; template <class T> inline T sqr(const T &x) {
return x * x;
} template <class T> inline int sgn(const T &x) {
const T eps = 1e-;
if (fabs(x) < eps) return ;
return x < ? - : ;
} struct point {
lf x, y;
point() {}
point(lf _x, lf _y) : x(_x), y(_y) {} inline point operator + (const point &p) const {
return point(x + p.x, y + p.y);
}
inline point operator - (const point &p) const {
return point(x - p.x, y - p.y);
}
inline lf operator * (const point &p) const {
return x * p.y - y * p.x;
}
inline point operator * (const lf &d) const {
return point(x * d, y * d);
}
inline void get() {
scanf("%lf%lf", &x, &y);
}
friend inline lf dis2(const point &p) {
return sqr(p.x) + sqr(p.y);
}
friend inline lf dis(const point &p) {
return sqrt(dis2(p));
}
} t[][], p[]; inline bool check(const point &a, const point &b, const point &c, const int &p) {
static lf T1[], T2[];
static int i;
T1[] = dis(a - b), T1[] = dis(b - c), T1[] = dis(c - a);
for (i = ; i < ; ++i)
T2[i] = dis(t[p][i] - t[p][i + ]);
sort(T1, T1 + ), sort(T2, T2 + );
for (i = ; i < ; ++i)
if (sgn(T1[i] - T2[i]) != ) return ;
return ;
} inline point get_cross(const point &a, const point &b, const point &c, const point &d) {
static lf rate;
rate = / ( - ((d - c) * (b - c)) / ((d - c) * (a - c)));
return (b - a) * rate + a;
} int main() {
int T, icase, i, j, f;
lf di[], d1;
point p1, a, b, c, d, e;
scanf("%d", &T);
for (icase = ; icase <= T; ++icase) {
f = ;
for (i = ; i < ; ++i) t[][i].get(), t[][i + ] = t[][i];
for (i = ; i < ; ++i) t[][i].get(), t[][i + ] = t[][i];
for (i = ; i < ; ++i) p[i].get(), p[i + ] = p[i]; for (i = ; i < ; ++i)
di[i] = dis(t[][i] - t[][i + ]), di[i + ] = dis(t[][i] - t[][i + ]);
if (((p[] - p[]) * (p[] - p[])) * ((p[] - p[]) * (p[] - p[])) < ) {
if (check(p[], p[], p[], ) && check(p[], p[], p[], )) f = ;
if (check(p[], p[], p[], ) && check(p[], p[], p[], )) f = ;
}
if (((p[] - p[]) * (p[] - p[])) * ((p[] - p[]) * (p[] - p[])) < ) {
if (check(p[], p[], p[], ) && check(p[], p[], p[], )) f = ;
if (check(p[], p[], p[], ) && check(p[], p[], p[], )) f = ;
} for (i = ; i < ; ++i) {
a = p[i], b = p[i + ], c = p[i + ], d = p[i + ];
if (((b - a) * (c - a)) * ((b - a) * (d - a)) < ) {
e = get_cross(a, b, c, d);
if (check(a, d, e, ) && check(b, c, e, )) f = ;
if (check(a, d, e, ) && check(b, c, e, )) f = ;
}
}
for (i = ; i < ; ++i) if (sgn((p[i + ] - p[i]) * (p[i + ] - p[i])) == ) {
d1 = dis(p[i + ] - p[i]);
for (j = ; j < ; ++j) if (d1 >= di[j]) {
p1 = p[i + ] - p[i];
p1 = p1 * (di[j] / d1) + p[i];
if (check(p[i + ], p[i], p1, ) && check(p[i + ], p[i + ], p1, )) f = ;
if (check(p[i + ], p[i], p1, ) && check(p[i + ], p[i + ], p1, )) f = ;
}
}
printf("Case #%d: %s\n", icase, f ? "Yes" : "No");
}
return ;
}