线段相交 POJ 2653

  1 // 线段相交 POJ 2653
  2 // 思路：数据比较水，据说n^2也可以过
  3 // 我是每次枚举线段，和最上面的线段比较
  4 // O(n*m)
  5 
  6 // #include <bits/stdc++.h>
  7 #include <iostream>
  8 #include <cstdio>
  9 #include <cstdlib>
 10 #include <algorithm>
 11 #include <vector>
 12 #include <math.h>
 13 using namespace std;
 14 #define LL long long
 15 typedef pair<int,int> pii;
 16 const double inf = 123456789012345.0;
 17 const LL MOD =100000000LL;
 18 const int N =1e5+10;
 19 #define clc(a,b) memset(a,b,sizeof(a))
 20 const double eps = 1e-8;
 21 void fre() {freopen("in.txt","r",stdin);}
 22 void freout() {freopen("out.txt","w",stdout);}
 23 inline int read() {int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;}
 24 
 25 int sgn(double x){
 26     if(fabs(x) < eps)return 0;
 27     if(x < 0)return -1;
 28     else return 1;
 29 }
 30 struct Point{
 31     double x,y;
 32     Point(){}
 33     Point(double _x,double _y){
 34         x = _x;y = _y;
 35     }
 36     Point operator -(const Point &b)const{
 37         return Point(x - b.x,y - b.y);
 38     }
 39     double operator ^(const Point &b)const{
 40         return x*b.y - y*b.x;
 41     }
 42     double operator *(const Point &b)const{
 43         return x*b.x + y*b.y;
 44     }
 45 };
 46 
 47 struct Line{
 48     Point s,e;
 49     int inx;
 50     Line(){}
 51     Line(Point _s,Point _e){
 52         s=_s;e=_e;
 53     }
 54     // pair<int,Point> operator & (const Line &b) const{
 55     //     Point res=s;
 56     //     if(sgn((s-e)^(b.s-b.e))==0){
 57     //         if(sgn((s-b.e)^(b.s-b.e))==0) 
 58     //             return make_pair(0,res);
 59     //         else  return make_pair(1,res);
 60     //     }
 61     //     double t=((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));
 62     //     res.x+=(e.x-s.x)*t;
 63     //     res.y+=(e.y-s.y)*t;
 64     //     return make_pair(2,res);
 65     // }
 66 };
 67 
 68 Line line[N];
 69 bool inter(Line l1,Line l2){
 70     return 
 71         max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) &&
 72         max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) &&
 73         max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) &&
 74         max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) &&
 75         sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s)) <= 0 &&
 76         sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s)) <= 0;
 77 }
 78 
 79 vector<Line> list;
 80 bool cmp(Line l1,Line l2){
 81     return l1.inx<l2.inx;
 82 }
 83 
 84 int main(){
 85     vector<Line>::iterator it;
 86     int n;
 87     while(~scanf("%d",&n),n){
 88         list.clear();
 89         for(int i=1;i<=n;i++){
 90            double x1,x2,y2,y1;
 91         scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
 92         line[i]=Line(Point(x1,y1),Point(x2,y2));
 93         line[i].inx=i;
 94     }
 95     list.push_back(line[1]);
 96     for(int i=2;i<=n;i++){
 97         for(it=list.begin();it!=list.end();){
 98            if(inter(line[i],*it)){
 99               it=list.erase(it);
100            }
101            else it++;
102         }
103         list.push_back(line[i]);
104     }
105     printf("Top sticks: ");
106     sort(line+1,line+1+list.size(),cmp);
107     for(it=list.begin();it!=list.end();it++){
108         if(it!=list.end()-1){
109             printf("%d, ",(*it).inx);
110         }
111         else printf("%d.
",(*it).inx);
112     }
113     }
114     return 0;
115 }