这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1086
判断两条直线是否相交,感觉这是一道非常不错的题,高中学的向量积,数量积都还给老师了(其实在高数上册最后也讲过),悲催啊~~~
这里有一篇非常给力的讲解:
http://dev.gameres.com/Program/Abstract/Geometry.htm
AC代码:
#include
using namespace std;
typedef struct line
{
double x1,y1,x2,y2;
}line;
int n;
line ln[105];
int mul(double a, double b, double c, double d)
{
return a * d - b * c;
}
bool judge(int i, int j)
{
double a = mul(ln[i].x1-ln[j].x1, ln[i].y1-ln[j].y1, ln[j].x2-ln[j].x1, ln[j].y2-ln[j].y1);
double b = mul(ln[i].x2-ln[j].x1, ln[i].y2-ln[j].y1, ln[j].x2-ln[j].x1, ln[j].y2-ln[j].y1);
double c = a * b;
double d = mul(ln[j].x1-ln[i].x1, ln[j].y1-ln[i].y1, ln[i].x2-ln[i].x1, ln[i].y2-ln[i].y1);
double e = mul(ln[j].x2-ln[i].x1, ln[j].y2-ln[i].y1, ln[i].x2-ln[i].x1, ln[i].y2-ln[i].y1);
double f = d * e;
if(c <= 0 && f <= 0)
return 1;
else
return 0;
}
int main()
{
//freopen("input.txt", "r", stdin);
while(scanf("%d", &n;) && n)
{
for(int i=1; i<=n; ++i)
scanf("%lf %lf %lf %lf", &ln;[i].x1, &ln;[i].y1, &ln;[i].x2, &ln;[i].y2);
int count=0;
for(int i=1; i
using namespace std;
double p[100][2],q[100][2];
// 判断点与直线的关系
double direction(double p[],double q[] ,double r[]){
return ((r[0]-p[0])*(q[1]-p[1])-(r[1]-p[1])*(q[0]-p[0]));
}
// 判断是否在线段构成的矩形内
bool onsegment(double p[],double q[], double r[]){
if(((r[0]-p[0])*(r[0]-q[0])<=0)&&((r[1]-p[1])*(r[1]-q[1])<=0))
return true;
else return false;
}
bool judge(int i, int j){
double d1,d2,d3,d4;
d1=direction(p[i],q[i],p[j]);
d2=direction(p[i],q[i],q[j]);
d3=direction(p[j],q[j],p[i]);
d4=direction(p[j],q[j],q[i]);
if((d1*d2<0)&&(d3*d4<0))
return true;
else if(d1==0&& onsegment(p[i],q[i],p[j])==1)
return true;
else if(d2==0&& onsegment(p[i],q[i],q[j])==1)
return true;
else if(d3==0&& onsegment(p[j],q[j],p[i])==1)
return true;
else if(d4==0&& onsegment(p[j],q[j],q[i])==1)
return true;
else return false;
}
int main(){
int n,i,j,count;
while(scanf("%d",&n;)){
if(n==0) break;
for(i=0;i<n;++i){
scanf("%lf %lf %lf %lf",&p[i][0],&p[i][1],&q[i][0],&q[i][1]);
}
for(i=0,count=0;i<n;i++)
for(j=i+1;j<n;j++)
if(judge(i,j)==1)
++count;
printf("%d\n",count);
}
return 0;
}