題目來源：http://poj.org/problem?id=2653

?

分析：

題意：按順序給出一些木棍，輸出在最上面的木棍標(biāo)號(hào)。

用vector 存儲(chǔ)木棍標(biāo)號(hào)， 當(dāng)前木棍與 vector 中的木棍 相交，則刪除該 木棍標(biāo)號(hào)， 注意vector.erase(it) 中 迭代指針的使用。

較簡(jiǎn)潔的寫法：

?

double add(double a, double b){return (fabs(a + b) < EPS * (fabs(a) + fabs(b))) ? 0 : (a + b) ; } struct Point{double x, y;Point(){}Point(double x, double y):x(x),y(y){}Point operator - (Point a){return Point( add(x , -a.x), add(y , -a.y)) ;}Point operator + (Point a){return Point( add(x , a.x), add(y , a.y)) ;}double operator ^(Point a){return add(x * a.y , -y * a.x) ;}}; bool on_segment(Point p1, Point p2, Point p){return ((p1 - p).x * (p2 - p).x <= 0 )&&((p1 - p).y * (p2 - p).y <= 0) ; } struct Line{Point st , ed ;Line(){}Line(Point s, Point e){st = s ;ed = e ;}bool intersection(Line l){Point p1, p2 ,q1 ,q2 ;p1 = st ;p2 = ed ;q1 = l.st ;q2 = l.ed ;double d1 ,d2 ,d3 ,d4;d1 = (p2 - p1)^(q1 - p1) ;d2 = (p2 - p1)^(q2 - p1) ;d3 = (q2 - q1)^(p1 - q1) ;d4 = (q2 - q1)^(p2 - q1) ;if((d1 == 0 && on_segment(p1, p2 ,q1))||(d2 == 0 && on_segment(p1, p2, q2))|| (d3 == 0 && on_segment(q1 ,q2 ,p1))|| (d4 == 0 && on_segment(q1,q2 ,p2)) )return 1;if(d1 * d2 < 0 && d3 * d4 < 0)return 1;return 0 ;}void read(){scanf("%lf%lf%lf%lf" , &st.x, &st.y ,&ed.x ,&ed.y);}}line[Max_N]; int n; bool ok(int i){for(int j = i+1 ; j < n ; j++){if(line[i].intersection(line[j]))return 0 ;}return 1 ; } vector<int>aa; vector<int>::iterator it; int main() {while(scanf("%d" , &n) && n){aa.clear() ;for(int i= 0 ; i < n ; i++){line[i].read() ;}for(int i = 0 ; i < n ; i++){if(ok(i))aa.push_back(i) ;}printf("Top sticks");int flag = 0 ;for(it = aa.begin() ; it != aa.end() ; it++){if(flag)printf(",") ;else printf(":") ;printf(" %d", (*it + 1)) ;flag = 1;}printf(".\n") ;}return 0 ; }

?

?

?

?

代碼如下：

?

#include <iostream> #include <algorithm> #include <stdlib.h> #include <stack> #include <iostream> #include <stdio.h> #include <string> #include <string.h> #include <algorithm> #include <stdlib.h> #include <vector> #include <set> #include <math.h> #include <cmath> #include <map> #include <stack> #include <queue>using namespace std ;double EPS=1e-10; // 考慮誤差的加法運(yùn)算 double add(double a,double b) {if(fabs(a+b)<EPS*(fabs(a)+fabs(b))) return 0;return a+b; } struct Point{double x,y;Point(){}Point(double x,double y):x(x),y(y){} // 構(gòu)造函數(shù)，方便代碼編寫Point operator +(Point p){return Point(add(x,p.x), add(y,p.y));}Point operator-(Point p){return Point(add(x,-p.x),add(y,-p.y));}Point operator*(double d){return Point(x*d,y*d);}double operator*(Point p){ // 內(nèi)積 點(diǎn)乘return add(x*p.x, y*p.y);}double operator^(Point p){// 外積 叉乘return add(x*p.y,-y*p.x);} }; //判斷點(diǎn)p0是否在線段p1p2內(nèi) int on_segment(Point p1, Point p2, Point p0) {if (((p1-p0).x * (p2-p0).x <=0 )&& ((p1-p0).y * (p2-p0).y <=0)) // 中間是 &&return 1;return 0; } // 判斷線段p1p2與q1是否相交 int intersection(Point p1,Point p2, Point q1,Point q2) {double d1=(p2-p1)^(q1-p1); // 計(jì)算p1p2 到q 點(diǎn)的轉(zhuǎn)向 d1>0 左轉(zhuǎn)， d1 <0 右轉(zhuǎn)double d2=(p2-p1)^(q2-p1);double d3=(q2-q1)^(p1-q1);double d4=(q2-q1)^(p2-q1);if((d1==0 && on_segment(p1,p2,q1) )|| (d2==0 && on_segment(p1,p2,q2) )||(d3==0&& on_segment(q1,q2,p1)) || (d4==0 && on_segment(q1,q2,p2)))return 1;else if(d1*d2<0 && d3*d4 <0) // 中間是 &&return 1;return 0; }struct Line{Point st ;Point ed ;Line(){}Line(Point a , Point b){st = a ;ed = b ;}void read(){scanf("%lf%lf%lf%lf" , &st.x , &st.y , &ed.x , &ed.y) ;} }; const int N = 100010; Line line[N]; vector<int>v; vector<int>::iterator it; void solve(int i) {for(it=v.begin(); it!= v.end(); ){if(intersection(line[i].st, line[i].ed,line[*it].st, line[*it].ed ) ){it=v.erase(it); // 刪除迭代指針為 it 處的元素， 并返回迭代指針。}else it++;} }int main() {int n;while(cin>>n && n){v.clear();for(int i=1;i<=n;i++){line[i].read();}for(int i=1;i<=n;i++){solve(i);v.push_back(i);}printf("Top sticks");int flag=0;for(it=v.begin() ; it != v.end(); it++){if(flag)printf(", ");else printf(": ");printf("%d",*it);flag=1;}printf(".\n");}return 0; }

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/zn505119020/p/3625958.html

總結(jié)

以上是生活随笔為你收集整理的判断线段相交 + vector. erase迭代指针 的使用 poj 2653 Pick-up sticks的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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