http://poj.org/problem?id=3304
给你几条线段 然后 让你找到一条直线让他在这条直线上的映射有一个重合点
如果有这条直线的话 这个重合的部分的两个端点一定是某两条线段的端点
所以只需要枚举每个点连成的直线能不能跟所有的线段相交就行了
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#include<math.h>
#define N 200
const double ESP = 1e-;
struct Point
{
double x, y; Point(double x=,double y=):x(x),y(y) {}
Point operator + (const Point &temp)const{
return Point(x+temp.x, y+temp.y);
}
Point operator - (const Point &temp)const{
return Point(x-temp.x, y-temp.y);
}
bool operator == (const Point &temp)const{
return (fabs(x-temp.x) < ESP && fabs(y-temp.y) < ESP);
}
int operator * (const Point &temp)const{
double t=(x*temp.y)-(y*temp.x);
if(t > ESP)
return ;
if(fabs(t) < ESP)
return ;
return -;
}
}; struct node
{
Point A,B;
node(Point A=,Point B=):A(A),B(B){} }; int Find(node t,node a[],int n)
{
for(int i=;i<n;i++)
{
int k=fabs((a[i].A-t.A)*(t.B-t.A)+(a[i].B-t.A)*(t.B-t.A)); if(k==)
return false;
}
return true;
} int main()
{
int n, T;
scanf("%d", &T);
while(T--)
{
Point p[N];
node a[N];
scanf("%d", &n);
double x1,x2,y2,y1;
int b=;
for(int i=;i<n;i++)
{
scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
p[b++]=Point(x1,y1);
p[b++]=Point(x2,y2);
a[i]=node(p[b-],p[b-]);
}
int ok=;
for(int i=; i<b && !ok; i++)
{
for(int j=i+; j<b && !ok; j++)
{
if(p[i] == p[j])
continue;
ok = Find(node(p[i],p[j]),a,n);
}
}
if(ok)
printf("Yes!\n");
else
printf("No!\n");
}
return ;
}