| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 9088 | Accepted: 2786 |
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!
给定n条线段，求能否找到一条直线，使得与所有线段相交，
枚举线段上所有点，然后暴力判定，注意一个坑爹的细节，会有两个点重合的情况。
代码：
/* ***********************************************
Author :rabbit
Created Time :2014/4/20 9:39:31
File Name :8.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-10
#define pi acos(-1.0)
typedef long long ll;
int dcmp(double x){
if(fabs(x)<eps)return 0;
return x>0?1:-1;
}
struct Point{
double x,y;
Point(double _x=0,double _y=0){
x=_x;y=_y;
}
};
Point operator + (Point a,Point b){
return Point(a.x+b.x,a.y+b.y);
}
Point operator - (Point a,Point b){
return Point(a.x-b.x,a.y-b.y);
}
Point operator * (Point a,double p){
return Point(a.x*p,a.y*p);
}
Point operator / (Point a,double p){
return Point(a.x/p,a.y/p);
}
bool operator < (const Point &a,const Point &b){
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
bool operator == (const Point &a,const Point &b){
return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double Dot(Point a,Point b){
return a.x*b.x+a.y*b.y;
}
double Length(Point a){
return sqrt(Dot(a,a));
}
double Angle(Point a,Point b){
return acos(Dot(a,b)/Length(a)/Length(b));
}
double angle(Point a){
return atan2(a.y,a.x);
}
double Cross(Point a,Point b){
return a.x*b.y-a.y*b.x;
}
Point vecunit(Point x){
return x/Length(x);
}
Point Normal(Point x){
return Point(-x.y,x.x);
}
Point Rotate(Point a,double rad){
return Point(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}
struct Line{
Point p,v;
double ang;
Line(){}
Line(Point P,Point v):p(P),v(v){
ang=atan2(v.y,v.x);
}
bool operator < (const Line &L) const {
return ang<L.ang;
}
Point point(double a){
return p+(v*a);
}
};
struct Seg{
Point s,e;
}pp[110];
int n;
bool judge(Point a,Point b){
//if(dcmp(Length(a-b))==0)return 0;
for(int i=0;i<n;i++)if(Cross(b-a,pp[i].s-a)*Cross(b-a,pp[i].e-a)>eps)return 0;
return 1;
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int T;
cin>>T;
while(T--){
cin>>n;
for(int i=0;i<n;i++)cin>>pp[i].s.x>>pp[i].s.y>>pp[i].e.x>>pp[i].e.y;
int flag=0;
for(int i=0;i<n&&!flag;i++){
if(judge(pp[i].s,pp[i].e))flag=1;
for(int j=i+1;j<n&&!flag;j++){
if(judge(pp[i].s,pp[j].s))flag=1;
if(judge(pp[i].s,pp[j].e))flag=1;
if(judge(pp[i].e,pp[j].s))flag=1;
if(judge(pp[i].e,pp[j].e))flag=1;
}
}
if(flag)puts("Yes!");
else puts("No!");
}
return 0;
}
POJ 3304 直线与线段关系,布布扣,bubuko.com
原文：http://blog.csdn.net/xianxingwuguan1/article/details/24203547