POJ 3304 Segments (叉乘判断线段相交)

时间:2022-09-06 10:10:04

<题目链接>

题目大意:

给出一些线段,判断是存在直线,使得该直线能够经过所有的线段。、

解题思路:

如果有存在这样的直线,过投影相交区域作直线的垂线,该垂线必定与每条线段相交,问题转化为问是否存在一条线和所有线段相交。

如果存在这么一条直线,那么该直线一定能够移成经过两个端点的形式。枚举所有线段的两个端点,判断该直线和所有线段是否相交即可。
#include <iostream>
#include <math.h>
#include <cstdio>
using namespace std;
#define MAXM 110
#define EPS 1e-8 //10的负8次方 typedef struct{
double x1,y1,x2,y2;
}Segment; //线段 Segment segment[MAXM];
int n; double distance(double x1,double y1,double x2,double y2){ //计算两点之间距离
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
} double corss(double x1,double y1,double x2,double y2,double x,double y){
return (x2-x1)*(y-y1)-(x-x1)*(y2-y1); //返回 (x2-x1,y2-y1) , (x-x1,y-y1)这两个向量的叉乘
} //根据的是(x,y)叉乘(b.x,b.y)=(x*b.y-y*b.x)公式;这个公式也可以通过三维向量叉乘的行列式得到,只不过要将这两个向量的Z坐标看成0 bool judge(double x1,double y1,double x2,double y2){
int i;
if(distance(x1,y1,x2,y2)<EPS) return ;
for(i=;i<n;i++){ //之所以是>ERS(ERS为无穷小),是因为若当前线段有一个端点是该分割线段的一个端点,此时答案应该是0,然而实际上0也是可以的,所以将ERS设为无穷小
if(corss(x1,y1,x2,y2,segment[i].x1,segment[i].y1)*corss(x1,y1,x2,y2,segment[i].x2,segment[i].y2)>EPS) return ;
//判断segment线段的两个端点是否置于该直线的两端
}
return ;
} int main(){
int t,i,j,flag;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=;i<n;i++)
scanf("%lf%lf%lf%lf",&segment[i].x1,&segment[i].y1,&segment[i].x2,&segment[i].y2);
if(n==) {printf("Yes!\n");continue;} flag=;
for(i=;i<n && !flag;i++){
for(int j=i+;j<n && !flag;j++){ //以任意两条线段的两个端点构成分割线,只要任意一条这样的分割线能够经过每一条线段,那么输出Yes
if(judge(segment[i].x1,segment[i].y1,segment[j].x1,segment[j].y1) ||
judge(segment[i].x1,segment[i].y1,segment[j].x2,segment[j].y2) ||
judge(segment[i].x2,segment[i].y2,segment[j].x1,segment[j].y1) ||
judge(segment[i].x2,segment[i].y2,segment[j].x2,segment[j].y2))
flag=;
}
}
if(flag) printf("Yes!\n");
else printf("No!\n");
}
return ;
}

2018-08-01

POJ 3304 Segments (叉乘判断线段相交)的更多相关文章

  1. POJ 3304 Segments (直线和线段相交判断)

    Segments Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 7739   Accepted: 2316 Descript ...

  2. POJ 2826 An Easy Problem&quest; 判断线段相交

    POJ 2826 An Easy Problem?! -- 思路来自kuangbin博客 下面三种情况比较特殊,特别是第三种 G++怎么交都是WA,同样的代码C++A了 #include <io ...

  3. 【POJ 2653】Pick-up sticks 判断线段相交

    一定要注意位运算的优先级!!!我被这个卡了好久 判断线段相交模板题. 叉积,点积,规范相交,非规范相交的简单模板 用了“链表”优化之后还是$O(n^2)$的暴力,可是为什么能过$10^5$的数据? # ...

  4. POJ 2653 Pick-up sticks(判断线段相交)

    Pick-up sticks Time Limit: 3000MS   Memory Limit: 65536K Total Submissions: 7699   Accepted: 2843 De ...

  5. POJ 3304 Segments (直线与线段是否相交)

    题目链接 题意 : 能否找出一条直线使得所有给定的线段在该直线上的投影有一个公共点. 思路 : 假设存在一条直线a使得所有线段在该直线上的投影有公共点,则必存在一条垂直于直线a的直线b,直线b与所有线 ...

  6. POJ 1066 - Treasure Hunt - &lbrack;枚举&plus;判断线段相交&rsqb;

    题目链接:http://poj.org/problem?id=1066 Time Limit: 1000MS Memory Limit: 10000K Description Archeologist ...

  7. POJ 2653 - Pick-up sticks - &lbrack;枚举&plus;判断线段相交&rsqb;

    题目链接:http://poj.org/problem?id=2653 Time Limit: 3000MS Memory Limit: 65536K Description Stan has n s ...

  8. nyoj-1016-德莱联盟(向量叉乘判断线段相交)

    叉乘的坐标表示: A(X1,Y1), B(X2, Y2), C(XC,YC), D(XD, YD);AB = (X2-X1, Y2-Y1);CD = (XD-XC, YD-YC); 向量AB,CD的叉 ...

  9. 【POJ 1556】The Doors 判断线段相交&plus;SPFA

    黑书上的一道例题:如果走最短路则会碰到点,除非中间没有障碍. 这样把能一步走到的点两两连边,然后跑SPFA即可. #include<cmath> #include<cstdio&gt ...

随机推荐

  1. aliyun阿里云Maven仓库地址——加速你的maven构建

    maven仓库用过的人都知道,国内有多么的悲催.还好有比较好用的镜像可以使用,尽快记录下来.速度提升100倍. http://maven.aliyun.com/nexus/#view-reposito ...

  2. myBatis总结,以及Spring

    myBatis是持久层框架.相对于hibernate是半自动的——手写sql语句,较灵活. myBatis中个人觉得主要是对sql语句的练习,对要实现业务层的功能在mapper.java中写出相应或辅 ...

  3. 【区间选点问题】uva 10148 - Advertisement

    区间选点问题,即数轴上有n个闭区间[l1i, ri],取尽量少的点,使得每个区间内都至少有一个点. The Department of Recreation has decided that it m ...

  4. easyUI 异步加载树

    $(function () { var selected = $('#depttree').tree('getSelected'); $('#depttree').tree({ checkbox: f ...

  5. Eclipse新建Java工程出现红色感叹号怎么解决?

    安装了新版本的JDK之后,在Eclipse中新建Java工程出现红色感叹号怎么解决? 其实只要在Eclipse中重新设置一下JDK路径就行了 路径:右键Java工程>>Build Path ...

  6. java 多线程简单例子

    实现线程的方式是一,继承Thread类,重写父类的run()方法 二,实现接口Runnable中的run()方法. 下面是简单的例子 例子1:银行存取钱问题 package com.direct.de ...

  7. rabbitmq学习(二):rabbitmq(消息队列)的作用以及rabbitmq之直连交换机

    前言 上篇介绍了AMQP的基本概念,组成及其与rabbitmq的关系.了解了这些东西后,下面我们开始学习rabbitmq(消息队列)的作用以及用java代码和rabbitmq通讯进行消息发布和接收.因 ...

  8. php基础和数据库

    服务器和客户端 客户端 程序: 通过浏览器直接运行 服务器 程序: 通过安装某种服务器软件   程序才可以运行              apache   php文件              tom ...

  9. Java考试题之六

    QUESTION 134 Given:11. class Snoochy {12. Boochy booch;13. public Snoochy() { booch = new Boochy(thi ...

  10. java回调方法之理解

    以前经常看见"回调方法(或回调函数)"一词,但是没有了解过是什么意思,更不知道用法.现在从网络上搜集了一些很好的资料,自己又整理一下,作为自己的笔记,也作为学习过程中的一个小脚印. ...