题意:给出n条线段,求是否有一条直线能够与全部线段相交.
由于一条穿过所有的线段的直线,总可以通过平移来使得其通过某两个端点,故枚举端点,判断过端点的直线是否能穿过所有线段即可.
此题WA几次..究其原因为: 叉积之前需要判断给出的向量是否为0,为0则不能进行叉积操作..
刚刚开始做计算几何…orz各路神犇..希望能够快快长进!
# include <iostream>
# include <cmath>
# define sqr(x) ((x)*(x))
# define rep(x, n) for (int x = 0; x < n; ++x )
using namespace std;
const double eps = 1e-8;
int dcmp(double x){ return (x > eps) - (x < -eps);}
class Point
{
public:
double x, y;
Point(){x = y = 0.0;}
Point(double a, double b){ x = a; y = b; }
inline Point operator -(const Point& b)
{ return Point(x-b.x, y-b.y);}
inline double cross(const Point& b, const Point& c)
{ return (b.x - x) * (c.y - y) - (c.x - x) * (b.y - y); }
inline double dis(const Point& b)
{ return sqrt( sqr(b.x - x) + sqr(b.y - y) ); }
}line[103][2];
int t, n;
bool ok;
void check(Point& a, Point& b)
{
if ( dcmp(a.dis(b)) == 0 ) return;
rep(i, n)
if ( dcmp(a.cross(b, line[i][0]) * a.cross(b, line[i][1])) > 0 )
return;
ok = true;
return;
}
int main()
{
double x, y;
cin >>t;
while( t-- )
{
cin >>n;
rep(i, n)
{
cin >> x >> y;
line[i][0] = Point(x, y);
cin >> x >> y;
line[i][1] = Point(x, y);
}
ok = false;
rep(i, n)
for (int j = i+1; j < n; ++j )
{
if ( ok ) break;
check(line[i][0], line[j][0]);
check(line[i][0], line[j][1]);
check(line[i][1], line[j][0]);
check(line[i][1], line[j][1]);
}
if ( n == 1 ) ok = true;
if ( ok ) cout << "Yes!" <<endl;
else cout << "No!" << endl;
}
return 0;
}