自己学做网站需要学多久,律师的网站模板,Wordpress用mvc开发吗,个人网站建设网站题目大意#xff1a;给出n条线段#xff0c;问是否存在一条直线#xff0c;使得n条线段在直线上的投影有至少一个公共点。 题目思路:如果假设成立#xff0c;那么作该直线的垂线l#xff0c;该垂线l与所有线段相交#xff0c;且交点可为线段中的某两个交点 证明#xff…题目大意给出n条线段问是否存在一条直线使得n条线段在直线上的投影有至少一个公共点。 题目思路:如果假设成立那么作该直线的垂线l该垂线l与所有线段相交且交点可为线段中的某两个交点 证明若有l和所有线段相交则可保持l和所有线段相交左右平移l到和某一线段交于端点停止“移不动了”。然后绕这个交点旋转。也是转到“转不动了”和另一线段交于其一个端点为止。这样就找到了一个新的l满足题意而且经过其中两线段的端点。 如何判断直线是否与线段相交如果线段的两个端点在直线的两侧那么线段与直线相交因此可利用叉积来经行判断。 #includeiostream
#includealgorithm
#includecstring
#includevector
#includestdio.h
#includestdlib.h
#includequeue
#includemath.h
#includemap
#define INF 0x3f3f3f3f
#define MAX 100005
#define Temp 1000000000
#define MOD 1000000007using namespace std;int n;struct node
{double x1,y1,x2,y2;
}a[MAX];int check(int pos,double x1,double y1,double x2,double y2)//求叉积
{double x3a[pos].x1,y3a[pos].y1,x4a[pos].x2,y4a[pos].y2;if(fabs(x1-x2)1e-8 fabs(y1-y2)1e-8)return 0;double op1(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);double op2(x2-x1)*(y4-y1)-(x4-x1)*(y2-y1);if(op1*op2 (1e-8))return 0;return 1;
}int Find(double x1,double y1,double x2,double y2)
{for(int i0;in;i){if(!check(i,x1,y1,x2,y2))return 0;}return 1;
}int solve()
{for(int i0;in;i)//枚举端点{for(int ji1;jn;j){if(Find(a[i].x1,a[i].y1,a[i].x2,a[i].y2))//上方线段return 1;if(Find(a[i].x1,a[i].y1,a[j].x1,a[j].y1))//两条线段左端连线return 1;if(Find(a[i].x1,a[i].y1,a[j].x2,a[j].y2))//两条线段左上右下连线return 1;if(Find(a[i].x2,a[i].y2,a[j].x1,a[j].y1))//两条线段右上左下连线return 1;if(Find(a[j].x1,a[j].y1,a[j].x2,a[j].y2))//下方线段return 1;if(Find(a[i].x2,a[i].y2,a[j].x2,a[j].y2))//两条线段有段连线return 1;}}return 0;
}int main()
{int T;scanf(%d,T);while(T--){scanf(%d,n);for(int i0;in;i){scanf(%lf%lf%lf%lf,a[i].x1,a[i].y1,a[i].x2,a[i].y2);}if(n3)//如果有一个或两个线段特判一下{printf(Yes!\n);continue;}int oksolve();if(ok)printf(Yes!\n);elseprintf(No!\n);}return 0;
} View Code 转载于:https://www.cnblogs.com/alan-W/p/5978520.html
