[原创]POJ 3304 Segments [枚举+叉乘判断线段相交]【计算几何】

2016-04-05 17:31:08 Tabris_ 阅读数：2158

博客爬取于2020-06-14 22:44:40
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/51066516

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

Segments
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 11920 Accepted: 3757

Description

Given n segments in the two dimensional space, write a program, which determines if there exists a line such that after projecting these segments on it, all projected segments have at least one point in common.

Input

Input begins with a number T showing the number of test cases and then, T test cases follow. Each test case begins with a line containing a positive integer n ≤ 100 showing the number of segments. After that, n lines containing four real numbers x1 y1 x2 y2 follow, in which (x1, y1) and (x2, y2) are the coordinates of the two endpoints for one of the segments.

Output

For each test case, your program must output “Yes!”, if a line with desired property exists and must output “No!” otherwise. You must assume that two floating point numbers a and b are equal if |a - b| < 10-8.

Sample Input

3
2
1.0 2.0 3.0 4.0
4.0 5.0 6.0 7.0
3
0.0 0.0 0.0 1.0
0.0 1.0 0.0 2.0
1.0 1.0 2.0 1.0
3
0.0 0.0 0.0 1.0
0.0 2.0 0.0 3.0
1.0 1.0 2.0 1.0
Sample Output

Yes!
Yes!
No!
Source

Amirkabir University of Technology Local Contest 2006

题目大意 ：
就是给你一堆线段 问你是否存在这样一条直线 使得所有线段在直线上的投影均有公共部分 有输出Yes 没有输出No

解题方法 ：
投影直线上有公共点的话就是说这条直线存在一个垂线经过所有线段 就是与所有线段均相交

只要枚举这些线段端点所确定的直线 是否存在一条与所有线段均相交即可

判断线段相交用的是叉乘 首先用两点p1,p2确定了一条直线 在用p1,p2分别与计算线段两个端点计算叉乘即可
叉乘之积>0就说明线段两端点在直线的同侧 也就是直线不经过此线段

注意 ：
本题是double类型
判断是否有重点 重点定义为坐标非常接近的两点 <1e-8即可
判断叉乘之积时 只要<1e-8 即可

附本题代码

这是引用网上与我代码非常接近的大神的代码 能Ac 但我的不知为什么就是不行 ~>_<~ 但也在下面贴出来了 如果有人找到BUG 了 一定要回复我 不胜感激

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
52
53
54
55
56
57
58
# include <iostream>
# include <math.h>
# include <cstdio>
using namespace std;
# define MAXM 110
# define EPS 1e-8

typedef struct{
    double x1,y1,x2,y2;
}Segment;

Segment segment[MAXM];
int n;

double distance(double x1,double y1,double x2,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

double corss(double x1,double y1,double x2,double y2,double x,double y){
    return (x2-x1)*(y-y1)-(x-x1)*(y2-y1);
}

bool judge(double x1,double y1,double x2,double y2){
    int i;
    if(distance(x1,y1,x2,y2)<EPS) return 0;
    for(i=0;i<n;i++){
        if(corss(x1,y1,x2,y2,segment[i].x1,segment[i].y1)*
            corss(x1,y1,x2,y2,segment[i].x2,segment[i].y2)>EPS) return 0;
    }
    return 1;
}

int main(){
    int t,i,j,ans;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%lf%lf%lf%lf",&segment[i].x1,&segment[i].y1,&segment[i].x2,&segment[i].y2);
        if(n==1) {printf("Yes!\n");continue;}

        ans=0;
        for(i=0;i<n && !ans;i++)
            for(j=i+1;j<n && !ans;j++){
                if(judge(segment[i].x1,segment[i].y1,segment[j].x1,segment[j].y1) ||
                    judge(segment[i].x1,segment[i].y1,segment[j].x2,segment[j].y2) ||
                    judge(segment[i].x2,segment[i].y2,segment[j].x1,segment[j].y1) ||
                    judge(segment[i].x2,segment[i].y2,segment[j].x2,segment[j].y2))
                    ans=1;
            }
        if(ans) printf("Yes!\n");
        else printf("No!\n");
    }
    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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
using namespace std;
int n,m;

//精度是个大问题啊  很重要  判断重点
const double eps = 1E-8;

struct point
{
    double  x,y;
} pzuo[1005],pyou[1005];

int dis (const point &p1,const point &p2)
{
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

int mul(const point &p1,const point &p2,const point &p3)
{
    return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}

int judge(const point &p1,const point &p2)
{
    if(dis(p1,p2)<eps)  return 0;
    for(int i=0; i<n; i++)
        if(mul(p1,p2,pzuo[i])*mul(p1,p2,pyou[i])>eps)
            return 0;

    return 1;
}

int solve()
{
    for(int i=0; i<n; i++)
        for(int j=i+1; j<n; j++)
            if(judge(pzuo[i],pzuo[j])||
                    judge(pzuo[i],pyou[j])||
                    judge(pyou[i],pzuo[j])||
                    judge(pyou[i],pyou[j]))
                return 1;

    return 0;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            scanf("%lf%lf%lf%lf",&pzuo[i].x,&pzuo[i].y,&pyou[i].x,&pyou[i].y);
        if(n==1)
        {
            printf("Yes!\n");
            continue;
        }
        if(solve())     printf("Yes!\n");
        else            printf("No!\n");
    }
    return 0;
}