471
POJ 3304 判斷直線與線段相交
題意：問存不存在一條直線，各個線段在直線上的投影有公共部分，也就是判斷是否存在一條直線將所有線段都相交。
枚舉所有端點構成的直線如果有一條直線相交所有線段那麼就存在。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define eps 1e-8
typedef double PointType;
struct point
{
PointType x,y;
};
PointType Direction(point pi,point pj,point pk) //判斷向量PiPj在向量PiPk的順逆時針方向 +順-逆0共線
{
return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
int main()
{
int t,n;
point data[405];
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0; i<n*2; i+=2)
scanf("%lf%lf%lf%lf",&data[i].x,&data[i].y,&data[i+1].x,&data[i+1].y);
int ans=0;
for(int i=0; i<2*n; i++)
{
for(int j=i+1; j<2*n; j++)
{
if(fabs(data[i].x-data[j].x)>eps||fabs(data[i].y-data[j].y)>eps)
{
ans=1;
for(int k=0; k<n*2; k+=2)
{
double d1=Direction(data[i],data[j],data[k]);
double d2=Direction(data[i],data[j],data[k+1]);
if(d1*d2>0)
{
ans=0;
break;
}
}
}
if(ans)
break;
}
if(ans)
break;
}
if(ans)
puts("Yes!");
else
puts("No!");
}
return 0;
}
最後更新：2017-04-03 22:30:57