专栏首页小L的魔法馆POJ 1410--Intersection(判断线段和矩形相交)

POJ 1410--Intersection(判断线段和矩形相交)

Intersection Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 16322 Accepted: 4213 Description

You are to write a program that has to decide whether a given line segment intersects a given rectangle.

An example: line: start point: (4,9) end point: (11,2) rectangle: left-top: (1,5) right-bottom: (7,1)

Figure 1: Line segment does not intersect rectangle

The line is said to intersect the rectangle if the line and the rectangle have at least one point in common. The rectangle consists of four straight lines and the area in between. Although all input values are integer numbers, valid intersection points do not have to lay on the integer grid. Input

The input consists of n test cases. The first line of the input file contains the number n. Each following line contains one test case of the format: xstart ystart xend yend xleft ytop xright ybottom

where (xstart, ystart) is the start and (xend, yend) the end point of the line and (xleft, ytop) the top left and (xright, ybottom) the bottom right corner of the rectangle. The eight numbers are separated by a blank. The terms top left and bottom right do not imply any ordering of coordinates. Output

For each test case in the input file, the output file should contain a line consisting either of the letter “T” if the line segment intersects the rectangle or the letter “F” if the line segment does not intersect the rectangle. Sample Input

1 4 9 11 2 1 5 7 1 Sample Output

F

  • 题目的判断是否一条线段和矩形相交,可以想到直接判断给定线段是否和矩形的四条边相交即可,但是有一个问题,题目定义的矩形”The rectangle consists of four straight lines and the area in between“,包括了其中的面积,就因为这个wa了几发Orz,我的等级还是不够啊。
  • 最后只要判断给定线段是否和矩形的四条边相交,以及线段是否在矩形内,线段是否在矩形内部可以用线段的端点是否在矩形内部来判断。
  • Code
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
double xs, ys, xe, ye, xl, yl, xr, yr;
const double eps = 1.0e8;
typedef struct point {
    double x;
    double y;
    point(double a, double b) {
        x = a;
        y = b;
    }
    point() {

    }
}point;
typedef struct edge {
    point start;
    point end;
    edge(point a, point b) {
        start = a;
        end = b;
    }
    edge() {

    }
    edge(edge &t) {
        start = t.start;
        end = t.end;
    }
}edge;
point t[4];
edge line;
edge rec[4];

inline double dabs(double a) { return a < 0 ? -a : a; }
inline double max(double a, double b) { return a > b ? a : b; }
inline double min(double a, double b) { return a < b ? a : b; }
double multi(point p1, point p2, point p0) {
    return (p2.y - p0.y)*(p1.x - p0.x) - (p2.x - p0.x)*(p1.y - p0.y);
}
bool Across(edge v1, edge v2) {
    if (max(v1.start.x, v1.end.x) >= min(v2.start.x, v2.end.x) &&
        max(v1.start.y, v1.end.y) >= min(v2.start.y, v2.end.y) &&
        max(v2.start.x, v2.end.x) >= min(v1.start.x, v1.end.x) &&
        max(v2.start.y, v2.end.y) >= min(v1.start.y, v1.end.y) &&
        multi(v2.start, v1.end, v1.start)*multi(v1.end, v2.end, v2.start) >= 0 &&
        multi(v1.start, v2.end, v2.start)*multi(v2.end, v1.end, v1.start) >= 0
        )
        return true;
    return false;
}
int main(void) {
    while (cin >> n) {
        while (n-- > 0) {
            int flag = 0;
            cin >> xs >> ys >> xe >> ye >> xl >> yl >> xr >> yr;
            line = edge(point(xs, ys), point(xe, ye));
            t[0] = point(xl, yl), t[1] = point(xr, yl);
            t[2] = point(xr, yr), t[3] = point(xl, yr);
            for (int i = 0; i < 4; i++) {
                rec[i] = edge(t[i], t[(i + 1)%4]);
            }
            for (int i = 0; i < 4; i++) {
                if (Across(line, rec[i]))
                {
                    flag = 1;
                    break;
                }
            }
            if(line.start.x>=min(xl,xr)&&line.start.x<=max(xr,xl)&&line.start.y>=min(yl,yr)&&line.start.y<=max(yl,yr) ||
                line.end.x >= min(xl, xr) && line.end.x <= max(xr, xl) && line.end.y >= min(yl, yr) && line.end.y <= max(yl, yr))
                    flag = 1;//判断是否点在矩形内部
            if (flag == 1)
                cout << "T" << endl;
            else
                cout << "F" << endl;
        }
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 网易云音乐为什么这么懂你?

    相信大家这几天的朋友圈已经被网易云音乐的年度听歌报告给刷屏了吧!不知道你们2018的年度关键词是什么,我的关键词是“青春”。

    谭庆波
  • 创业者注意了!大数据教你如何在众筹网站上成功融资

    有好点子,想创业,但没钱,怎么办?Kickstarter是美国著名的众筹网站,在这里可以帮有好点子的创业者实现梦想!本文数据侠抓取了Kickstarter的众筹...

    DT数据侠
  • 鸿篇巨制 —— LevelDB 的整体架构

    本节信息量很大,我们要从整体上把握 LevelDB 这座大厦的结构。当我们熟悉了整体的结构,接下来就可以各个击破来细致了解它的各种微妙的细节了。

    老钱
  • KVC赋值取值过程分析

    前面我们简单使用了KVC, 发现KVC能够对私有的成员进行取值赋值, 那么KVC的赋值取值的过程是什么样的?了解下..

    CC老师
  • Optimization of Machine Learning

    机器学习就是需要找到模型的鞍点,也就是最优点。因为模型很多时候并不是完全的凸函数,所以如果没有好的优化方法可能会跑不到极值点,或者是局部极值,甚至是偏离。所以选...

    西红柿炒鸡蛋
  • BAT 经典算法笔试题: 镜像二叉树

    再过不到 2 个月,互联网行业就要再次迎来面试高峰了。为了让大家能顺利通过所有面试环节必经的笔试阶段,我提前给大伙准备了一套常见的算法笔试题。这套算法题来源于 ...

    老钱
  • iOS多线程研究(四)

    这里是一张高清无码大图,如果直接走下载,然后加载UI,整个程序就会有堵塞。 解决办法就是开启异步线程,进行下载,最后回到UI更新

    CC老师
  • BAT 经典算法笔试题 —— 逆转单向链表

    不善言谈的优秀程序员在面试中往往是要吃巨亏的,你没有办法通过说话来轻易证明自己的实力。不论是大厂还是小厂,大部分面试官都不具备优秀的面试能力,它们也只能通过三言...

    老钱
  • 数学原来这么有趣,66组超炫动图唤醒你的思维!

    无论怎样,看完这一组动图,你不仅能够感受到数学美丽的一面,同时也会对我们常见的公式定理有更深刻、直观的理解!

    华章科技
  • EM Algorithm

    EM算法和之前学的都不太一样,EM算法更多的是一种思想,所以后面用几个例子讲解,同时也会重点讲解GMM高斯混合模型。

    西红柿炒鸡蛋

扫码关注云+社区

领取腾讯云代金券