文档章节

POJ_2653_Pick-up sticks_線線相交

電泡泡
 電泡泡
发布于 2013/10/08 22:46
字数 259
阅读 93
收藏 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
博文 183
码字总数 69717
作品 0
衡阳
在工程图中如何进行虚拟相交点标注

在工程圖中, 線段被[倒圓角]後,如何找出[虛擬相交]點進行標註。請參考以下說明: 1. 打開工程圖任一線段圓角。 2. 將智慧草圖的 [交點] 與 [延伸] 關係勾選。 3. 使用 [間距]標註,類型用 [2...

solidedge
2015/09/07
103
0
netstat 检查异常网络连接

netstat 是一個十分好用的網絡管理工具,而其中一個用途是查看不尋常連線,例如當一個 IP 發送大量連線到伺服器,那麼伺服器很大機會是否遭受 DoS 或 DDoS 攻擊。 以下是一些實用的 netstat ...

鉴客
2014/04/03
248
0
Andorid Looper入门使用介绍

public class Looper extends Object Class Overview Class used to run a message loop for a thread. Threads by default do not have a message loop associated with them; to create on......

程序袁_绪龙
2015/08/07
0
0
PyQt 這個問題如何解決 QPixmap: It is not safe to use pixmaps outside the GUI thread

我正在寫一個遠程桌面程序,PyQt的做介面&使用PyQt庫捕獲屏幕,因為需要管理GUI和捕獲屏幕所以我用兩個線程,一個線程管理GUI,另一個線程負責捕獲屏幕和發送圖像但有一個錯誤QPixmap 不能工...

jacklam
2013/10/02
1K
0
Android开发中的NinePatch圖檔

传统UI开发中,如果背景的大小不一样,一般需要为每种大小都 制作一张图片,这在button中尤为明显。当然我们也可以一小块一小块水平重复的画,也可 以垂直的话。在android中专门有一种叫nin...

囧南风囧
2010/11/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

你为什么在Redis里读到了本应过期的数据

一个事故的故事 晚上睡的正香突然被电话吵醒,对面是开发焦急的声音:我们的程序在访问redis的时候读到了本应过期的key导致整个业务逻辑出了问题,需要马上解决。 看到这里你可能会想:这是不...

IT--小哥
今天
2
0
祝大家节日快乐,阖家幸福! centos GnuTLS 漏洞

yum update -y gnutls 修复了GnuTLS 漏洞。更新到最新 gnutls.x86_64 0:2.12.23-22.el6 版本

yizhichao
昨天
5
0
Scrapy 1.5.0之选择器

构造选择器 Scrapy选择器是通过文本(Text)或 TextResponse 对象构造的 Selector 类的实例。 它根据输入类型自动选择最佳的解析规则(XML vs HTML): >>> from scrapy.selector import Sele...

Eappo_Geng
昨天
4
0
Windows下Git多账号配置,同一电脑多个ssh-key的管理

Windows下Git多账号配置,同一电脑多个ssh-key的管理   这一篇文章是对上一篇文章《Git-TortoiseGit完整配置流程》的拓展,所以需要对上一篇文章有所了解,当然直接往下看也可以,其中也有...

morpheusWB
昨天
5
0
中秋快乐!!!

HiBlock
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部