題目鏈接：點(diǎn)擊查看

題目大意：給出n條線(xiàn)段，現(xiàn)在問(wèn)是否存在一條直線(xiàn)，使得所有線(xiàn)段向這條直線(xiàn)的投影存在一個(gè)共同的交點(diǎn)

題目分析：題意有點(diǎn)抽象，需要轉(zhuǎn)換一下，因?yàn)樗械木€(xiàn)段向某一條直線(xiàn)的投影存在一個(gè)交點(diǎn)，那么在那條直線(xiàn)上，從交點(diǎn)位置開(kāi)始，沿著垂直于直線(xiàn)的方向做另一條直線(xiàn)，會(huì)發(fā)現(xiàn)這條直線(xiàn)與n條線(xiàn)段都存在一個(gè)交點(diǎn)，也就是都相交，這樣題目就轉(zhuǎn)換為了是否存在一條直線(xiàn)，使得與n條線(xiàn)段都有交點(diǎn)

因?yàn)橹本€(xiàn)也是由兩個(gè)點(diǎn)組成的，我們枚舉所有線(xiàn)段上的點(diǎn)，作為構(gòu)成直線(xiàn)上的兩個(gè)點(diǎn)，每次判斷一下是否滿(mǎn)足條件即可，時(shí)間復(fù)雜度為(2*n)*(2*n)*n，因?yàn)閚比較小，所以直接實(shí)現(xiàn)就行了

有個(gè)細(xì)節(jié)需要注意一下，可能會(huì)有兩個(gè)點(diǎn)重合的情況，這個(gè)時(shí)候需要特判一下

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=110;const double eps = 1e-8;int n;int sgn(double x){if(fabs(x) < eps)return 0;if(x < 0)return -1;else return 1; }struct Point{double x,y;Point(){}Point(double _x,double _y){x = _x;y = _y;}void input(){scanf("%lf%lf",&x,&y);}double distance(Point p){return hypot(x-p.x,y-p.y);}Point operator -(const Point &b)const{return Point(x-b.x,y-b.y);}//叉積double operator ^(const Point &b)const{return x*b.y - y*b.x;}//點(diǎn)積double operator *(const Point &b)const{return x*b.x + y*b.y;} };struct Line{Point s,e;Line(){}Line(Point _s,Point _e){s = _s;e = _e;}void input(){s.input();e.input();}//`直線(xiàn)和線(xiàn)段相交判斷`//`-*this line -v seg`//`2 規(guī)范相交`//`1 非規(guī)范相交`//`0 不相交`int linecrossseg(Line v){int d1 = sgn((e-s)^(v.s-s));int d2 = sgn((e-s)^(v.e-s));if((d1^d2)==-2) return 2;return (d1==0||d2==0);} }line[N];bool check(Line l) {if(sgn(l.s.distance(l.e))==0)return false;for(int i=1;i<=n;i++)if(!l.linecrossseg(line[i]))return false;return true; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;while(w--){vector<Point>point;scanf("%d",&n);for(int i=1;i<=n;i++){line[i].input();point.push_back(line[i].s);point.push_back(line[i].e);}for(int i=0;i<point.size();i++)for(int j=0;j<point.size();j++)if(check(Line(point[i],point[j]))){puts("Yes!");goto end;}puts("No!"); end:;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的POJ - 3304 Segments(简单几何)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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