題目大意：給出n條線段，問(wèn)是否存在一條直線，使得n條線段在直線上的投影有至少一個(gè)公共點(diǎn)。

題目思路:如果假設(shè)成立，那么作該直線的垂線l，該垂線l與所有線段相交，且交點(diǎn)可為線段中的某兩個(gè)交點(diǎn)

證明：若有l(wèi)和所有線段相交，則可保持l和所有線段相交，左右平移l到和某一線段交于端點(diǎn)停止（“移不動(dòng)了”）。然后繞這個(gè)交點(diǎn)旋轉(zhuǎn)。也是轉(zhuǎn)到“轉(zhuǎn)不動(dòng)了”（和另一線段交于其一個(gè)端點(diǎn)）為止。這樣就找到了一個(gè)新的l滿足題意，而且經(jīng)過(guò)其中兩線段的端點(diǎn)。

如何判斷直線是否與線段相交：如果線段的兩個(gè)端點(diǎn)在直線的兩側(cè)，那么線段與直線相交，因此可利用叉積來(lái)經(jīng)行判斷。

#include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<stdio.h> #include<stdlib.h> #include<queue> #include<math.h> #include<map> #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 x3=a[pos].x1,y3=a[pos].y1,x4=a[pos].x2,y4=a[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 i=0;i<n;i++){if(!check(i,x1,y1,x2,y2))return 0;}return 1; }int solve() {for(int i=0;i<n;i++)//枚舉端點(diǎn) {for(int j=i+1;j<n;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 i=0;i<n;i++){scanf("%lf%lf%lf%lf",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);}if(n<3)//如果有一個(gè)或兩個(gè)線段特判一下 {printf("Yes!\n");continue;}int ok=solve();if(ok)printf("Yes!\n");elseprintf("No!\n");}return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/alan-W/p/5978520.html

總結(jié)

以上是生活随笔為你收集整理的Segments POJ 3304 直线与线段是否相交的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。