poj 2653（线段相交）

第一道计算几何题。。。。

试用了下两种删除vector中元素的方法。

第一种使用：（每次erase一个元素后都会指向下一个元素位置）

1 for(int j=0;j<v.size();)
2 {
3     if(intersect_in(lin[i],lin[v[j]]))
4         v.erase(v.begin()+j);
5     else
6         j++;
7 }

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <vector>
 7 
 8 using namespace std;
 9 
10 #define eps 1e-8
11 #define PI acos(-1.0)//3.14159265358979323846
12 //判断一个数是否为0,是则返回true,否则返回false
13 #define zero(x)(((x)>0?(x):-(x))<eps)
14 //返回一个数的符号，正数返回1，负数返回2，否则返回0
15 #define _sign(x)((x)>eps?1:((x)<-eps?2:0))
16 
17 const int maxn =  1e5+5;
18 struct point 
19 {
20     double x,y;
21 };
22 struct line
23 {
24     point a,b;
25     line(){}
26     line(double x1,double y1,double x2,double y2)
27     {
28         a.x=x1;
29         a.y=y1;
30         b.x=x2;
31         b.y=y2;
32     }
33 };
34 line lin[maxn];
35 double xmult(point p1,point p2,point p0)
36 {
37     return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
38 }
39 //计算dotproduct(P1-P0).(P2-P0)
40 double dmult(point p1,point p2,point p0)
41 {
42     return(p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y);
43 }
44 //判三点共线
45 int dots_inline(point p1,point p2,point p3)
46 {
47     return zero(xmult(p1,p2,p3));
48 }
49 //判点是否在线段上,包括端点
50 int dot_online_in(point p,line l)
51 {
52     return zero(xmult(p,l.a,l.b))&&(l.a.x-p.x)*(l.b.x-p.x)<eps&&(l.a.y-p.y)*(l.b.y-p.y)<eps;
53 }
54 //判两点在线段同侧,点在线段上返回0
55 int same_side(point p1,point p2,line l)
56 {
57     return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)>eps;
58 }
59 
60 int intersect_in(line u,line v)
61 {
62     if(!dots_inline(u.a,u.b,v.a)||!dots_inline(u.a,u.b,v.b))//规范相交
63         return!same_side(u.a,u.b,v)&&!same_side(v.a,v.b,u);
64     return dot_online_in(u.a,v)||dot_online_in(u.b,v)||dot_online_in(v.a,u)||dot_online_in(v.b,u);
65 }
66 
67 int main()
68 {
69     int n;
70     double x1,x2,y1,y2;
71     while(scanf("%d",&n))
72     {
73         if(!n) break;
74         vector<int>v;
75         for(int i=1;i<=n;i++)
76         {
77             scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
78             lin[i]=line(x1,y1,x2,y2);
79             for(int j=0;j<v.size();)
80             {
81                 if(intersect_in(lin[i],lin[v[j]]))
82                     v.erase(v.begin()+j);
83                 else
84                     j++;
85             }
86             v.push_back(i);
87         }
88         printf("Top sticks:");
89         for(int i=0;i<v.size()-1;i++)
90             printf(" %d,",v[i]);
91         printf(" %d.\n",v[v.size()-1]);
92     }
93     return 0;
94 }

第二种使用remove_if()。

 1 line tmp;
 2 bool ok(line l)
 3 {
 4     if(intersect_in(tmp,l))
 5         return true;
 6     else
 7         return false;
 8 }
 9 
10 v.erase(remove_if(v.begin(),v.end(),ok),v.end());

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <vector>
  7 
  8 using namespace std;
  9 
 10 #define eps 1e-8
 11 #define PI acos(-1.0)//3.14159265358979323846
 12 //判断一个数是否为0,是则返回true,否则返回false
 13 #define zero(x)(((x)>0?(x):-(x))<eps)
 14 //返回一个数的符号，正数返回1，负数返回2，否则返回0
 15 #define _sign(x)((x)>eps?1:((x)<-eps?2:0))
 16 
 17 struct point 
 18 {
 19     double x,y;
 20 };
 21 struct line
 22 {
 23     point a,b;
 24     int id;
 25     line(){}
 26     line(double x1,double y1,double x2,double y2,int i)
 27     {
 28         a.x=x1;
 29         a.y=y1;
 30         b.x=x2;
 31         b.y=y2;
 32         id=i;
 33     }
 34 };
 35 double xmult(point p1,point p2,point p0)
 36 {
 37     return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
 38 }
 39 //计算dotproduct(P1-P0).(P2-P0)
 40 double dmult(point p1,point p2,point p0)
 41 {
 42     return(p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y);
 43 }
 44 //判三点共线
 45 int dots_inline(point p1,point p2,point p3)
 46 {
 47     return zero(xmult(p1,p2,p3));
 48 }
 49 //判点是否在线段上,包括端点
 50 int dot_online_in(point p,line l)
 51 {
 52     return zero(xmult(p,l.a,l.b))&&(l.a.x-p.x)*(l.b.x-p.x)<eps&&(l.a.y-p.y)*(l.b.y-p.y)<eps;
 53 }
 54 //判两点在线段同侧,点在线段上返回0
 55 int same_side(point p1,point p2,line l)
 56 {
 57     return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)>eps;
 58 }
 59 
 60 int intersect_in(line u,line v)
 61 {
 62     if(!dots_inline(u.a,u.b,v.a)||!dots_inline(u.a,u.b,v.b))//规范相交
 63         return!same_side(u.a,u.b,v)&&!same_side(v.a,v.b,u);
 64     return dot_online_in(u.a,v)||dot_online_in(u.b,v)||dot_online_in(v.a,u)||dot_online_in(v.b,u);
 65 }
 66 
 67 line tmp;
 68 bool ok(line l)
 69 {
 70     if(intersect_in(tmp,l))
 71         return true;
 72     else
 73         return false;
 74 }
 75 
 76 int main()
 77 {
 78     int n;
 79     double x1,x2,y1,y2;
 80     while(scanf("%d",&n))
 81     {
 82         if(!n) break;
 83         vector<line>v;
 84         for(int i=1;i<=n;i++)
 85         {
 86             scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
 87             tmp=line(x1,y1,x2,y2,i);
 88             v.erase(remove_if(v.begin(),v.end(),ok),v.end());
 89             /*for(int j=0;j<v.size();)
 90             {
 91                 if(intersect_in(lin[i],lin[v[j]]))
 92                     v.erase(v.begin()+j);
 93                 else
 94                     j++;
 95             }*/
 96             v.push_back(tmp);
 97             
 98         }
 99         printf("Top sticks:");
100         for(int i=0;i<v.size()-1;i++)
101             printf(" %d,",v[i].id);
102         printf(" %d.\n",v[v.size()-1].id);
103     }
104     return 0;
105 }