HDU/HDOJ 1086 You can Solve a Geometry Problem too

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1086

判断两条直线是否相交,感觉这是一道非常不错的题,高中学的向量积,数量积都还给老师了(其实在高数上册最后也讲过),悲催啊~~~

这里有一篇非常给力的讲解:

http://dev.gameres.com/Program/Abstract/Geometry.htm

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>  
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<n; ++i)  
        {  
            for(int j=i+1; j<=n; ++j)  
                if(judge(i,j)) 
                    ++count;  
        }  
        cout << count << endl;  
    }  
    return 0;  
}

网上另外一种版本,其实方法是一样的,顺便贴出来:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDU/HDOJ 1086 You can Solve a Geometry Problem too》有473个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注