poj3304Segments(直线与多条线段相交)

链接

枚举两点(端点),循环遍历与直线相交的线段。

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 105
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
struct point
{
double x,y;
point(double x=,double y = ):x(x),y(y){}
}p[N<<];
struct line
{
point a,b;
};
typedef point pointt ;
pointt operator -(point a,point b)
{
return point(a.x-b.x,a.y-b.y);
}
int dcmp(double x)
{
if(fabs(x)<eps) return ;
return x<?-:;
}
double cross(point a,point b)
{
return a.x*b.y-a.y*b.x;
}
double xmult(point a,point b,point c)
{
return cross(a-c,b-c);
}
int dotline(point p,line l)
{
return (!dcmp(xmult(p,l.a,l.b)))&&(l.a.x-p.x)*(l.b.x-p.x)<eps
&&(l.a.y-p.y)*(l.b.y-p.y)<eps;
}
double dis(point a)
{
return sqrt(a.x*a.x+a.y*a.y);
}
int Intersection( point a,point b,point c,point d )
{
int d1,d2;
d1 = dcmp(xmult( a,c,b ));
d2 = dcmp(xmult( a,d,b ));
if( d1*d2==- ) return ;//规范相交
if( d1==||d2== ) return ;//非规范相交
return ;//不相交
}
int main()
{
int t,i,j,n,g;
cin>>t;
while(t--)
{
cin>>n;
for(i= ; i <= n; i++)
{
scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i+n].x,&p[i+n].y);
}
if(n==||n==)
{
puts("Yes!");
continue;
}
int flag = ;
for(i = ; i <= *n; i++)
{
for(j = i+; j<= *n; j++)
{
line l1;
l1.a = p[i],l1.b = p[j];
if(dcmp(dis(p[i]-p[j]))==) continue;
int num = ;
for(g = ; g <= n ;g++)
{
if(Intersection(p[i],p[j],p[g],p[g+n])) num++;
else break;
}
if(num==n)
{
flag = ;
break;
}
}
if(flag) break;
}
if(flag) puts("Yes!");
else puts("No!");
}
return ;
}
上一篇:windows下使用mingw编译出ffplay(简化版)


下一篇:刨根问底U3D---从Profile中窥探Unity的内存管理