POJ_2653_Pick-up sticks_線線相交
POJ_2653_Pick-up sticks_線線相交
電泡泡 发表于4年前
POJ_2653_Pick-up sticks_線線相交
  • 发表于 4年前
  • 阅读 59
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】如何购买服务器最划算?>>>   

#include <stdio.h>//POJ_2653_Pick-up sticks_線線相交
#include <stdlib.h>
#define EPS 1e-9


struct point{
    double x,y;
};
struct Line{
    point p1,p2;
}line[100002];


double MAX(double a,double b){
    return a>b?a:b;
}


double MIN(double a,double b){
    return a>b?b:a;
}


double mulit(point p0,point p1,point p2){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}


int cross(Line a,Line b){//判断两线段是否相交
    if(MAX(a.p1.x,a.p2.x)>MIN(b.p1.x,b.p2.x)&&
        MAX(b.p1.x,b.p2.x)>MIN(a.p1.x,a.p2.x)&&
        MAX(a.p1.y,a.p2.y)>MIN(b.p1.y,b.p2.y)&&
        MAX(b.p1.y,b.p2.y)>MIN(a.p1.y,a.p2.y)&&
        mulit(a.p1,a.p2,b.p1)*mulit(a.p1,a.p2,b.p2)<EPS&&
        mulit(b.p1,b.p2,a.p1)*mulit(b.p1,b.p2,a.p2)<EPS)
        return 1;
    return 0;
}


int main(void)
{
    int n,i,j;
    while(1){
        scanf("%d",&n);
        if(n==0)break;
        for(i=1;i<=n;i++){
            scanf("%lf%lf%lf%lf",&line[i].p1.x,&line[i].p1.y,&line[i].p2.x,&line[i].p2.y);
        }
        printf("Top sticks:");
        for(i=1;i<=n-1;i++){
            for(j=i+1;j<=n;j++){
                if(cross(line[i],line[j]))
                    break;
                if(j==n) //若没有其他筷子与其相交,则该筷子是最上面筷子之一


                    printf(" %d,",i);
            }
        }
        printf(" %d.\n",n);
    }
    return 0;
}

 
 
 
 

  
  
共有 人打赏支持
粉丝 25
博文 181
码字总数 69717
×
電泡泡
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: