回 帖 发 新 帖 刷新版面

主题:[讨论]这题我也不会,讲个方法

不接触矩形【rect.pas】
[问题描述]
    在二维棋盘上有N(1<=N<=30000)个矩形,它们的四条边都在棋盘线上。这些矩形互不相交,但是可能接触(如果棋盘上一个点在两个矩形的边上,则这两个矩形互相接触)。但是有些矩形和其它的任何矩形互不接触,这些矩形我们称作不接触矩形。
    给出每个矩形的点坐标(都在0到10^9范围内),求这个棋盘上不接触矩形的个数。
[输入文件]
    输入文件rect.in的第一行有一个数N(1<=N<=30000),表示矩形个数。
    接下来N行,每行四个数,分别表示一个矩形的左上角坐标和右下角坐标。
    输入数据都是正确的,不用判错。
[输出文件]
    输出文件rect.out只有一个数,表示不接触矩形的个数,若没有则输出0。
[输入样例]
    4
    0 3 2 5
    3 4 5 9
    4 2 7 4
    7 0 9 2
[输出样例]
    1

回复列表 (共6个回复)

沙发

矩形的面积是多少?

板凳

这题跟矩形面积没关系吧!

3 楼

数据较少,可以用最朴素的方法

4 楼

30000个还算少??

5 楼

可不可以先用数组把n*n的用数组都附上1,再用4个循环把矩形的个个点(包括边上的点)在赋上原数-然后在判断如果有矩形的每条边上的点都是零就把得数+1,最后打印出得数。

6 楼

楼上的算法,时间、空间复杂度会高得吓人的。

我来回复

您尚未登录,请登录后再回复。点此登录或注册