Segments---poj3304(判断直线与线段的位置关系)

题目链接:http://poj.org/problem?id=3304

题意:给你n个线段,求是否有一条直线与所有的线段都相交,有Yes,没有No;

枚举所有的顶点作为直线的两点,然后判断这条直线是否和所有的线段相交即可;注意不能找两个相同的点作为直线上的两点;

#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<stdio.h>
#include<queue>
using namespace std;
#define met(a, b) memset(a, b, sizeof(a))
#define mod 1000000007
typedef long long LL;
const int N = ;
const int INF = 0x3f3f3f3f;
const double eps = 1e-; struct point
{
double x, y;
point(double x=, double y=) : x(x), y(y) {}
friend point operator -(point p1, point p2)
{
return point(p1.x-p2.x, p1.y-p2.y);
}
friend int operator ^(point p1, point p2)
{
double k = p1.x*p2.y - p1.y*p2.x; if(k > eps) return ;
if(fabs(k) < eps) return ;
return -;
}
friend int operator ==(point p1, point p2)
{
return (p1.x == p2.x && p1.y == p2.y);
}
}p[N]; struct line
{
point s, e;
line(point s=, point e=) : s(s), e(e) {}
}Line[N]; int Judge(line l, line L[], int n)
{
for(int i=; i<=n; i++)
{
int k = abs( ((l.s-l.e)^(L[i].s-l.e)) + ((l.s-l.e)^(L[i].e-l.e)) );
///判断直线l是否与线段L[i]相交;
if(k == ) return ;///不相交;
}
return ;
} int main()
{
int T, n;
scanf("%d", &T);
while(T--)
{
met(p, );
met(Line, ); int k = ;
scanf("%d", &n);
for(int i=; i<=n; i++)
{
double x1, x2, y1, y2;
scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
p[k++] = point(x1, y1);
p[k++] = point(x2, y2);
Line[i] = line(p[k-], p[k-]);
}
int flag = ;
for(int i=; i<k && !flag; i++)
{
for(int j=; j<i && !flag; j++)
{
if(p[i] == p[j]) continue;
flag = Judge(line(p[i], p[j]), Line, n);
}
}
if(flag) puts("Yes!");
else puts("No!");
}
return ;
}
上一篇:Java计算器1.0版


下一篇:LightOj1190 - Sleepwalking(判断点与多边形的位置关系--射线法模板)