View Code of Problem 2334

#include<stdio.h>
#include<stdlib.h>
#define Max 100001
typedef struct node
{
    double x1,y1,x2,y2;
}Point;
Point p[Max];
int n,count;
int visted[Max];
void Init()
{
    int i;
    for(i = 1;i <= n;i ++)
        visted[i] = 0;
}
int check(int a,int b)                //关键在于怎么计算两线段a,b是否相交,这里用叉积的知识判断
{
    //计算叉积
    double x1,y1,x,y,x3,y3,t,f;
    x1 = p[a].x1 - p[b].x2; y1 = p[a].y1 - p[b].y2;
    x = p[a].x1 - p[a].x2;y = p[a].y1 - p[a].y2;            //(x,y)代表线段a
    x3 = p[a].x1 - p[b].x1;y3 = p[a].y1 - p[b].y1;
    t = (x1*y-x*y1)*(x3*y-x*y3);
    if(t > 0)
        return 0;
    else if(t == 0)                                         //有共线时，需要判断端点在线段上还是在延长线上
    {
        t = x1/x; f = y1/y;
        if(t == f){
            if(t < 0||t > 1)
                return 0;
        }
        t = x3/x;
        if(t < 0||t > 1)
            return 0;
    }
    x1 = p[b].x1 - p[a].x1; y1 = p[b].y1 - p[a].y1;
    x = p[b].x1 - p[b].x2;y = p[b].y1 - p[b].y2;              //(x,y)代表线段b
    x3 = p[b].x1 - p[a].x2;y3 = p[b].y1 - p[a].y2;
    t = (x1*y-x*y1)*(x3*y-x*y3);
    if(t > 0)
        return 0;
    else if(t == 0)                                         //有共线时，需要判断端点在线段上还是在延长线上
    {
        t = x1/x; f = y1/y;
        if(t == f){
            if(t < 0||t > 1)
                return 0;
        }
        t = x3/x;
        if(t < 0||t > 1)
            return 0;
    }
    return 1;
}
void solve(int x)
{
    int i;
    for(i = 1;i < x;i ++){
        if(!visted[i]){
           // printf("ok\n");
            if(check(x,i)){
                visted[i] = 1;
               // printf("i = %d\n",i);
                count ++;
            }
        }
    }
}
int main(void)
{
    int i = 1;
    while(scanf("%d",&n) && n!=0)
    {
        Init();
        count = 0;
        scanf("%lf %lf %lf %lf",&p[i].x1,&p[i].y1,&p[i].x2,&p[i].y2);
        for(i = 2;i <= n;i ++){
            scanf("%lf %lf %lf %lf",&p[i].x1,&p[i].y1,&p[i].x2,&p[i].y2);
            solve(i);
        }
        count = n - count;
        //printf("count = %d\n",count);
        printf("Top sticks:");
        for(i = 1;i <= n;i ++)
            if(visted[i] == 0){
                if(count == 1)
                    printf(" %d",i);
                else
                    printf(" %d,",i);
                count --;
            }
        printf(".\n");
    }
}