判断线段相交 + vector. erase迭代指针 的使用 poj 2653 Pick-up sticks

#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;
// 考虑误差的加法运算
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){} // 构造函数，方便代码编写
    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){  // 内积 点乘
        return add(x*p.x, y*p.y);
    }
    double operator^(Point p){//  外积 叉乘
        return add(x*p.y,-y*p.x);
    }
};
//判断点p0是否在线段p1p2内
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);           // 计算p1p2 到q 点的转向 d1>0 左转，  d1 <0 右转
    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;
}