ZOJ 1648 Circuit Board(计算几何)

Circuit Board Time Limit: 2 Seconds Memory Limit: 65536 KB On the circuit board, there are lots of circuit paths. We know the basic constrain is that no two path cross each other, for otherwise the board will be burned.

Now given a circuit diagram, your task is to lookup if there are some crossed paths. If not find, print “ok!”, otherwise “burned!” in one line.

A circuit path is defined as a line segment on a plane with two endpoints p1(x1,y1) and p2(x2,y2).

You may assume that no two paths will cross each other at any of their endpoints.

Input

The input consists of several test cases. For each case, the first line contains an integer n(<=2000), the number of paths, then followed by n lines each with four float numbers x1, y1, x2, y2.

Output

If there are two paths crossing each other, output “burned!” in one line; otherwise output “ok!” in one line.

Sample Input

1 0 0 1 1

2 0 0 1 1 0 1 1 0

Sample Output

ok! burned!

直接用模板,判断两个线段是否相交

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
struct Point
{
    double x,y;
}a[2005][2];
int n;
double mult(Point a, Point b, Point c)
{
    return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}

//aa, bb为一条线段两端点 cc, dd为另一条线段的两端点 相交返回true, 不相交返回false
bool intersect(Point aa, Point bb, Point cc, Point dd)
{
    if ( max(aa.x, bb.x)<min(cc.x, dd.x) )
    {
        return false;
    }
    if ( max(aa.y, bb.y)<min(cc.y, dd.y) )
    {
        return false;
    }
    if ( max(cc.x, dd.x)<min(aa.x, bb.x) )
    {
        return false;
    }
    if ( max(cc.y, dd.y)<min(aa.y, bb.y) )
    {
        return false;
    }
    if ( mult(cc, bb, aa)*mult(bb, dd, aa)<0 )
    {
        return false;
    }
    if ( mult(aa, dd, cc)*mult(dd, bb, cc)<0 )
    {
        return false;
    }
    return true;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%lf%lf%lf%lf",&a[i][0].x,&a[i][0].y,&a[i][1].x,&a[i][1].y);
        bool tag=true;
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                if(intersect(a[i][0],a[i][1],a[j][0],a[j][1]))
                {tag=false;break;}
            }
            if(!tag)
                break;
        }
        if(!tag)
            printf("burned!\n");
        else
           printf("ok!\n");
    }
    return 0;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

POJ 3278 Catch That Cow(BFS,板子题)

Catch That Cow Time Limit: 2000MS Memory Limit: 65536K Total Submissions...

2955
来自专栏数据结构与算法

BZOJ1901: Zju2112 Dynamic Rankings(整体二分 树状数组)

给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1

842
来自专栏小樱的经验随笔

Codefoces 723B Text Document Analysis

B. Text Document Analysis time limit per test:1 second memory limit per test:256...

35510
来自专栏轻扬小栈

[半zz]迅雷笔试题

1663
来自专栏机器学习入门

LWC 63: 750. Number Of Corner Rectangles

LWC 63: 750. Number Of Corner Rectangles 传送门:750. Number Of Corner Rectangles Pr...

2297
来自专栏idba

了解Python装饰器

一 装饰器是什么 装饰器是一个用于封装函数或者类的代码工具,显式地将封装器作用于函数或者类上,达到程序运行时动态增加功能的目的。对于函数运行前处理常见前置条件...

976
来自专栏10km的专栏

fastjson:javabean按字段(field)序列化存储为Map并反序列化改进

需求说明 最近的项目应用到redis数据库,需要将java bean存储在redis数据库。因为需要对数据库中的某个字段进行修改,所以在redis上不能用简单的...

2168
来自专栏Android知识点总结

写一个自定义控件attrs自动生成代码工具

894
来自专栏C语言及其他语言

[每日一题]C语言程序设计教程(第三版)课后习题6.1

题目描述 输入两个正整数m和n,求其最大公约数和最小公倍数。 输入 两个整数 输出 最大公约数,最小公倍数 样例输入 5 7 样例输出 1 35 提示 此类题目...

3023
来自专栏desperate633

LeetCode 350. Intersection of Two Arrays II题目分析代码

样例 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].

1136

扫码关注云+社区