文档章节

sicily 1004 I Conduit!

Ciel
 Ciel
发布于 2012/12/17 12:16
字数 816
阅读 159
收藏 0

Description

Irv Kenneth Diggit works for a company that excavates trenches, digs holes and generally tears up people's yards. Irv's job is to make sure that no underground pipe or cable is underneath where excavation is planned. He has several different maps, one for each utility company, showing where their conduits lie, and he needs to draw one large, consolidated map combining them all. One approach would be to simply draw each of the smaller maps one at a time onto the large map. However, this often wastes time, not to mention ink for the pen-plotter in the office, since in many cases portions of the conduits overlap with each other (albeit at different depths underground). What Irv wants is a way to determine the minimum number of line segments to draw given all the line segments from the separate maps.

Input

Input will consist of multiple input sets. Each set will start with a single line containing a positive integer n indicating the total number of line segments from all the smaller maps. Each of the next n lines will contain a description of one segment in the format x1 y1 x2 y2 where (x1,y1) are the coordinates of one endpoint and (x2,y2) are the coordinates of the other. Coordi- nate values are floating point values in the range 0... 1000 specified to at most two decimal places. The maximum number of line segments will be 10000 and all segments will have non-zero length. Following the last input set there will be a line containing a 0 indicating end of input; it should not be processed.

Output

For each input set, output on a single line the minimum number of line segments that need to be drawn on the larger, consolidated map.

Sample Input

3
1.0 10.0 3.0 14.0
0.0 0.0 20.0 20.0
10.0 28.0 2.0 12.0
2
0.0 0.0 1.0 1.0
1.0 1.0 2.15 2.15
2
0.0 0.0 1.0 1.0
1.0 1.0 2.15 2.16
0

Sample Output

2
1
2

分析:

本题比较水,主要要注意浮点数的相等判断处理,以及输入数据存储顺序的整理,然后排序统计即可。特别注意的是,本题的数据是线段,不是直线,所以能否合并要判断两条共线线段的相邻端点;还有点斜式无法表示垂直于x轴的直线,这里不妨设它斜率为正无穷(赋个很大的数即可),同时端点判断也要特殊处理。

代码:

// Problem#: 1004
// Submission#: 1792749
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

#define MAX 10000
#define INF 1000000
#define ESP 1e-6

struct node{
    double x1,y1,x2,y2;
    double k,b;
}buffer[MAX];

inline bool dcmp( double a, double b ){
    return ( fabs(a-b)<=ESP );
}

inline double max( double a, double b ){
    return a>b?a:b;
}

inline void swap( double &a, double &b ){
    double t = a;
    a = b;
    b = t;
}

inline bool cmp( node a, node b ){
    if( !dcmp(a.k,b.k) ) return a.k<b.k;
    if( !dcmp(a.b,b.b) ) return a.b<b.b;
    if( !dcmp(a.x1,b.x1) ) return a.x1<b.x1;
    if( !dcmp(a.y1,b.y1) ) return a.y1<b.y1;
    if( !dcmp(a.x2,b.x2) ) return a.x2<b.x2;
    return a.y2<b.y2;
}

inline bool judge( node a, node b ){
    if( dcmp(a.k,b.k) && dcmp(a.b,b.b) ){
        if( dcmp(a.k,INF) ) return dcmp(b.y1,a.y2) || b.y1<a.y2;
        else return  dcmp(a.x2,b.x1) || a.x2>b.x1;
    }
    return false;
}

int main(){
    int n,re;
    while( cin>>n && n ){
        re = n;
        for( int i=0 ; i<n ; i++ ){
            cin >> buffer[i].x1 >> buffer[i].y1 >> buffer[i].x2 >> buffer[i].y2;
            bool flag = dcmp(buffer[i].x1,buffer[i].x2);
            if( flag && buffer[i].y1>buffer[i].y2 ) swap(buffer[i].y1,buffer[i].y2);
            else if( !flag && buffer[i].x1>buffer[i].x2 ){
                swap(buffer[i].x1,buffer[i].x2);
                swap(buffer[i].y1,buffer[i].y2);
            }
            buffer[i].k = flag ? INF : (buffer[i].y2-buffer[i].y1) / (buffer[i].x2-buffer[i].x1);
            buffer[i].b = flag ? buffer[i].x1 : buffer[i].y1-buffer[i].k*buffer[i].x1;
        }
        sort(buffer,buffer+n,cmp);
        for( int i=0 ; i<n-1 ; i++ ){
            if( judge(buffer[i],buffer[i+1]) ){
                re--;
                if( dcmp(buffer[i].k,INF) ) buffer[i+1].y2 = max(buffer[i].y2,buffer[i+1].y2);
                else
                    buffer[i+1].x2 = max(buffer[i].x2,buffer[i+1].x2);
            }
        }
        cout << re << endl;
    }
    return 0;
}

© 著作权归作者所有

Ciel
粉丝 3
博文 24
码字总数 18532
作品 0
程序员
私信 提问
Oracle 11g R2 ADG 搭建

--============Oracle ADG搭建============== --==========准备阶段========= 1.检查primary为archivelog模式。 select log_mode from v$database; 如果为noarchivelog模式,切换到archivelo......

UltraSQL
2018/07/23
0
0
基于 Kubernetes 的 Service Mesh 开源解决方案 - Conduit

Conduit 是 Rust 语言开发的超轻量级 service mesh。 Conduit 的目标是成为最快、最轻、最简单并且最安全的 Service Mesh。他使用 Rust 构建了快速、安全的数据平面,用 Go 开发了简单强大的...

匿名
2017/12/28
2.9K
3
Conduit 0.5 成为终曲,后续并入 Linkerd 2.0

在 Conduit 0.5 的发布公告中,官方表示,0.5 版本将成为 Conduit 的最后一个主要版本,Conduit 将逐步整合进 Linkerd 项目,成为 Linkerd 2.0 的基础继续存在。 Conduit 是一个 Kubernetes...

h4cd
2018/07/10
2.1K
10
如期而至:正在走向生产之路的Conduit v0.2.0 里程碑版本发布

作者:GEORGE MIRANDA Release Note 转自:伪架构师(公众号ID:fake-architect) 原文:Announcing Conduit support for HTTP/1.x and TCP 我们很高兴地宣布,最新的 Conduit 发布了一个重大...

ServiceMesh中文网
2018/02/05
0
0
Conduit 宣布推出 Chrome App 开发平台

Conduit 是一个提供浏览器自定义工具条和托管 Web 应用程序的公司,已经几乎兼容了所有的浏览器。今天,该公司宣布正式推出针对 Chrome 的 Web 应用开发平台,新的平台可以让开发者创建并分享...

红薯
2010/06/03
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

linux 磁盘不足异常

linux 报 No space left on device 异常 ,则是磁盘不足 ,导致异常 运行 df -h 命令查询磁盘使用率,如果有100%,则查找目录大日志文件删除 1.磁盘不足导致系统应用写入文件失败,如系统日志...

zaolonglei
29分钟前
3
0
即学即用的 30 段 Python 实用代码

☞ 分享:最全最新的Python学习大礼包 ☜ 点击查看 编译:Pita & AI开发者,作者:Fatos Morina Python是目前最流行的语言之一,它在数据科学、机器学习、web开发、脚本编写、自动化方面被许...

Object_Man
30分钟前
3
0
The server time zone value 'EDT' is unrecognized or represents more than one time zone.

2019-10-14 18:07:43.714 ERROR 74363 --- [Druid-ConnectionPool-Create-1855026648] com.alibaba.druid.pool.DruidDataSource : create connection SQLException, url: jdbc:mysql://10.30......

yizhichao
43分钟前
8
0
html加载顺序以及影响页面二次渲染额的因素

本文转载于:专业的前端网站➱html加载顺序以及影响页面二次渲染额的因素 浏览器请求发往服务器以后,返回HTML页面,页面内容开始渲染,具体的执行顺序为: 1. 浏览器开始载入html代码,发现<...

前端老手
45分钟前
9
0
BeginnersBook JSP、JSTL、Servlet 教程

来源:ApacheCN BeginnersBook 翻译项目 译者:飞龙 协议:CC BY-NC-SA 4.0 贡献指南 本项目需要校对,欢迎大家提交 Pull Request。 请您勇敢地去翻译和改进翻译。虽然我们追求卓越,但我们并...

ApacheCN_飞龙
57分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部