思路：若所有线段在直线l上的投影有公共点p，那我们可以形象地说，（由投影的定义）必有一束细光穿过所有线段，投到直线l上，且在之上形成了一个光点p。
那么，是否有这么一束光呢？如何求呢？
方法：枚举两两线段的各一个端点，连一条直线，再判断剩下的线段是否都和这条直线有交点。
证明：为什么只需每次枚举两个端点就行了呢？首先假设这条直线不过任何端点，则我们可以左右平移这条直线，直到“脱离”了某个线段，此时与某个端点a相交；然后再将直线绕点a旋转，直到又“脱离”了一条线段，此时直线与另一端点相交，这就是我们需要的直线。证毕。
陷阱：可能有两条线段有一个端点重合，请跳过这种情况。
完整代码：
/*16ms,352KB*/ #include#include const int mx = 105; const double eps = 1e-8; struct point { double x, y; //point(double x = 0, double y = 0): x(x), y(y) {} } p[2 * mx]; ///计算p1p2 x p1p double cross_product(point p1, point p2, point p) { return (p2.x - p1.x) * (p.y - p1.y) - (p2.y - p1.y) * (p.x - p1.x); } bool judge(int n) { int i, j, k; for (i = 0; i < n; ++i) { for (j = 0; j < n; ++j) { if (fabs(p[i].x - p[j].x) < eps && fabs(p[i].y - p[j].y) < eps) continue; ///两点重合 for (k = 0; k < n; k += 2) if ( cross_product(p[i], p[j], p[k]) * cross_product(p[i], p[j], p[k + 1]) > 0 ) break; ///直线pi-pj与线段p1k-p2k不相交 if (k == n) return true; } } return false; } int main() { int t, n, i, j; scanf(%d, &t); while (t--) { scanf(%d, &n); n <<= 1; for (i = 0; i < n; ++i) scanf(%lf%lf, &p[i].x, &p[i].y); if (n <= 4) puts(Yes!); else puts(judge(n) Yes! : No!); } return 0; }