题目:题目链接
题意:就是给你N条线段。问你是不是存在这样一条线段,使得所有的点都和这些线段相交
分析:存在一条直线穿过所有的线段。那么我们找任意两个端点,然后判断这两个端点构成的线段是不是和所有的直线
相交。如果找到一条就直接return true即可:
代码:
#include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <stack> #include <functional> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cassert> #include <bitset> #include <stack> #include <ctime> #include <list> #define INF 0x7fffffff #define max3(a,b,c) (max(a,b)>c?max(a,b):c) #define min3(a,b,c) (min(a,b)<c?min(a,b):c) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; int QuickMod(int a,int b,int n) { int r = 1; while(b) { if(b&1) r = (r*a)%n; a = (a*a)%n; b >>= 1; } return r; } #define maxn 210 #define eps 1e-8 int sig(double d) { return (d > eps) - (d < -eps); } struct Point { double x, y; } point[maxn]; int n; double cross(const Point &o, const Point &a, const Point &b) { return (a.x - o.x)*(b.y - o.y) - (a.y - o.y)*(b.x - o.x); } int segLineCross(const Point &a, const Point &b, const Point &c, const Point &d) { int d1, d2;//看到的判断两条线端相交的写法..... d1 = sig(cross(a, b, c)); d2 = sig(cross(a, b, d)); if((d1 ^ d2) == -2) return 1;//标准相交 if(d1 == 0 || d2 == 0) return 2;//不标准 return 0;//不 } bool test(const Point &a, const Point &b) { if(sig(a.x - b.x) == 0 && sig(a.y - b.y) == 0) return false; for(int i = 1; i <= 2*n; i += 2) { if(segLineCross(a, b, point[i], point[i+1]) == 0) return false ; } return true; } bool find() { for(int i = 1; i < 2*n; ++i) { for(int j = i+1; j <= 2*n; ++j) if(test(point[i], point[j])) return true; } return false; } int main() { int t; scanf("%d", &t); while(t--) { scanf("%d", &n); for(int i = 1; i <= 2*n; ++i) scanf("%lf%lf", &point[i].x, &point[i].y); if(find()) printf("Yes!\n"); else printf("No!\n"); } }