题目链接 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 了 一定要回复我 不胜感激
#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;
}
我那错误的代码>_<
#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;
}