文档章节

POJ_2653_Pick-up sticks_線線相交

電泡泡
 電泡泡
发布于 2013/10/08 22:46
字数 259
阅读 98
收藏 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
衡阳
私信 提问
netstat 检查异常网络连接

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

鉴客
2014/04/03
270
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
2018/04/06
0
0
HTC Hero(G3)官方Android 2.1升级发布

来自HTC台湾官网的消息,数次跳票的G3 Hero官方Android 2.1版系统升级今天正式发布。 HTC官网在今天中午更新公告,表示将会提供HTC Hero固件的无线更新,本次更新以空中OTA升级的方式放出,用...

鉴客
2010/06/07
607
1

没有更多内容

加载失败,请刷新页面

加载更多

求推广,德邦快递坑人!!!!

完全没想好怎么来吐槽自己这次苦逼的德邦物流过程了,只好来记一个流水账。 从寄快递开始: 2019年1月15日从 德邦物流 微信小app上下单,截图如下: 可笑的是什么,我预约的是17号上门收件,...

o0无忧亦无怖
昨天
3
0
Mac Vim配置

1.升级 vim   我自己 MacBook Pro 的系统还是 10.11 ,其自带的 vim 版本为 7.3 ,我们将其升至最新版: 使用 homebrew : brew install vim --with-lua --with-override-system-vim 这将下...

Pasenger
昨天
4
0
vmware安装Ubuntu上不了网?上网了安装不了net-tools,无法执行ifconfig?

1.重新设置网络适配器还是不行,如下指定nat 2.还需要指定共享网络,我是在无线环境下 3.无法执行ifconfig https://packages.ubuntu.com/bionic/net-tools到这个网站下载net-tools的deb文件...

noob_chr
昨天
1
0
解决SVN:E210007无法协商认证机制

svn:E210007 svn: Cannot negotiate authentication mechanism 执行下面代码即可 sudo yum install cyrus-sasl cyrus-sasl-plain cyrus-sasl-ldap...

临江仙卜算子
昨天
2
0
java8的时间和`Date`的对比

java8的时间和Date的对比 java8提供了新的时间接口。相对Date,Calendar,个人感觉最大的好处是对时间操作的学习成本很低,比Calendar低。 1. LocalDate,LocalTime,LocalDateTime LocalDate 代...

北风刮的不认真了
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部