QOJ.ac

QOJ

时间限制: 2.0 s 内存限制: 2048 MB 总分: 100

#16041. 有多少个正方形?

统计

在网上冲浪时(当然是用没有安装任何广告拦截器的 Internet Explorer),你注意到各种网页的侧边栏广告中有很多有趣的竞赛。在大多数此类竞赛中,你需要回答一个简单的问题,比如图片中有多少个三角形/正方形/长方形,甚至只需从三个选项中选择正确答案。尽管任务很简单,但似乎有很多珍贵的奖品等着你拿。所以这绝对值得一试!

血细胞计数板,一种用于计数血细胞的装置;由 Jeffrey M. Vinocur 拍摄,遵循 CC BY 2.5 协议

为了增加获奖几率,你决定写一个简单的程序来帮你解决这个问题。你决定先专注于“图片中有多少个正方形?”这个问题。为了进一步简化问题,你假设输入的图片仅由若干条双向无限延伸的直线组成。具体来说,我们称图片中的四条直线 $\ell_1, \ell_2, \ell_3, \ell_4$ 构成一个正方形,如果直线 $\ell_1$ 和 $\ell_3$ 互相平行,且均垂直于 $\ell_2$ 和 $\ell_4$,并且 $\ell_1$ 与 $\ell_3$ 之间的距离等于 $\ell_2$ 与 $\ell_4$ 之间的距离。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 2\,000$),表示输入图片中的直线数量。

接下来 $n$ 行,每行包含对输入图片中一条直线的描述。每条直线由其上的两个不同点给出。也就是说,描述包含四个整数 $x_1, y_1, x_2, y_2$,每个数的绝对值最多为 $10\,000$,表示直线通过点 $(x_1, y_1)$ 和 $(x_2, y_2)$。你可以假设点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 是不同的,并且图片中的所有直线两两不同。

输出格式

输出仅一行,包含一个整数,表示由图片中的直线构成的正方形总数。

样例

输入样例 1

10
0 0 1 0
0 1 1 1
0 2 2 2
0 0 0 4
1 -1 1 0
2 -2 2 2
1 1 2 2
1 1 0 2
3 1 2 2
1 3 0 2

输出样例 1

6

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.