文档章节

POJ_2653_Pick-up sticks_線線相交

電泡泡
 電泡泡
发布于 2013/10/08 22:46
字数 259
阅读 95
收藏 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;
}

 
 
 
 

  
  

© 著作权归作者所有

共有 人打赏支持
上一篇: ACM中java快速入门
下一篇: hdu 1541 树状数组
電泡泡
粉丝 24
博文 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
在 YouTube 網址後面加上 my 就能快速下載、備份影片 Mp4 格式

(Copyright: emevil / 123RF Stock Photo) 很多人會選擇將影片上傳到 YouTube 或 Facebook 分享,即使是使用於個人網站、部落格,也會利用內嵌方式節省流量,不過上傳到網路後必須考量到日...

w116858389
04/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

FinderWeb2.4.9 程序员的看日志利器

FinderWeb2.4.9 程序员的看日志利器 使用方法:管理员登录,分配对应用户的的主机和文件权限即可。 部署方式: 下载并解压到webapps目录即可 http://www.finderweb.net/download/finder-web...

吴伟祥
26分钟前
1
0
PHP的pcntl进程控制教程一(pcntl_fork)

pcntl 简介 PHP的进程控制支持实现了Unix方式的进程创建, 程序执行, 信号处理以及进程的中断。 进程控制不能被应用在Web服务器环境,当其被用于Web服务环境时可能会带来意外的结果。 这份文档...

hansonwong
32分钟前
1
0
php扩展模块安装

11月21日任务 11.32 php扩展模块装安装 /usr/local/php/bin/php -m //查看模块 下面安装一个redis的模块 cd /usr/local/src/ wget https://codeload.github.com/phpredis/phpredis/zip/deve......

zgxlinux
32分钟前
3
0
windows下使用IDEA创建VUE项目

1.环境搭建 1.1检测是否安装好nodejs和npm 检测命令 node -v npm -v 如果没有安装需要先安装 nodejs的下载路径:https://nodejs.org/en/download/ 在Windows上安装时务必选择全部组件,包括勾...

文文1
40分钟前
3
0
Mybatis插件plugin应用测试,替换查询sql

1、新建插件 import org.apache.ibatis.executor.CachingExecutor;import org.apache.ibatis.executor.Executor;import org.apache.ibatis.executor.parameter.ParameterHandler;im......

jcc_codingBoy
44分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部