poj2653——Pick-up sticks（判断线段是否相交）-白红宇

poj2653——Pick-up sticks（判断线段是否相交）

阅读量：2343 次

发布时间：2019-05-10

本文共 2784 字，大约阅读时间需要 9 分钟。

Description

Stan has n sticks of various length. He throws them one at a time on the floor in a random way. After finishing throwing, Stan tries to find the top sticks, that is these sticks such that there is no stick on top of them. Stan has noticed that the last thrown stick is always on top but he wants to know all the sticks that are on top. Stan sticks are very, very thin such that their thickness can be neglected.

Input

Input consists of a number of cases. The data for each case start with 1 <= n <= 100000, the number of sticks for this case. The following n lines contain four numbers each, these numbers are the planar coordinates of the endpoints of one stick. The sticks are listed in the order in which Stan has thrown them. You may assume that there are no more than 1000 top sticks. The input is ended by the case with n=0. This case should not be processed.

Output

For each input case, print one line of output listing the top sticks in the format given in the sample. The top sticks should be listed in order in which they were thrown.

The picture to the right below illustrates the first case from input.

Sample Input

1 1 4 2

2 3 3 1

1 -2.0 8 4

1 4 8 2

3 3 6 -2.0

0 0 1 1

1 0 2 1

2 0 3 1

Sample Output

Top sticks: 2, 4, 5.

Top sticks: 1, 2, 3.

按顺序丢出一些线段，给出这些线段的坐标，求哪些线段是在上面的。

如果一条直线没有与之后丢出的线段相交，那么这个线段就在上面，判断线段相交的方法以前似乎也看到过，不过当时不懂，现在算是看懂了。

首先坐标不能违规，总不能说第二条线段最左端都大于第一条线段的最右端，上下也是一样的。

然后把这两条线段看成向量，如果它们相交的话，a的某个端点与b的两个端点相连后，a本身一定是在两条连线的中间，也就是说两条连线一定在a本身的两端，因此它们的叉积方向不一样，以此就可以判断是否相交。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #define INF 0x3f3f3f3f#define MAXN 100010#define Mod 10001using namespace std;struct point{ double x,y; point() {} point(double xx,double yy) { x=xx; y=yy; } point operator -(const point &b) { return point(x-b.x,y-b.y); } double operator ^(const point &b) { return x*b.y-y*b.x; }};struct Line{ point s,e; Line() {} Line(point ss,point ee) { s=ss; e=ee; }};Line line[MAXN];int top[MAXN];bool inter(Line a,Line b){ return max(a.s.x,a.e.x)>=min(b.s.x,b.e.x)&& max(b.s.x,b.e.x)>=min(a.s.x,a.e.x)&& max(a.s.y,a.e.y)>=min(b.s.y,b.e.y)&& max(b.s.y,b.e.y)>=min(a.s.y,b.s.y)&& ((b.s-a.s)^(a.s-a.e))*((b.e-a.s)^(a.s-a.e))<=0&& ((a.s-b.s)^(b.s-b.e))*((a.e-b.s)^(b.s-b.e))<=0;}int main(){ int n; while(~scanf("%d",&n)&&n) { double x1,y1,x2,y2; for(int i=1; i<=n; ++i) { scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); line[i]=Line(point(x1,y1),point(x2,y2)); top[i]=1; } for(int i=1; i<=n; ++i) { for(int j=i+1; j<=n; ++j) { if(inter(line[i],line[j])) { top[i]=0; break; } } } printf("Top sticks: "); bool flag=true; for(int i=1; i<=n; ++i) { if(top[i]) { if(flag) flag=false; else printf(", "); printf("%d",i); } } printf(".\n"); } return 0;}

转载地址：http://ltcvb.baihongyu.com/

你可能感兴趣的文章

下面关于HTTP协议的说法正确的是：----腾讯2016研发工程师笔试题（一）