QOJ.ac

QOJ

حد الوقت: 1 s حد الذاكرة: 1024 MB مجموع النقاط: 100

#11963. 围栏费用

الإحصائيات

国家作物保护委员会(NCPC)致力于通过提供与农田面积成比例的补贴来支持当地农民。每位农民可以拥有多个农田,每个农田的形状各异,但在几何上被定义为一个多边形,由仅在顶点处相交的栅栏围成。

在官僚主义的典型表现中,为了激励形状良好的农田,NCPC 将根据农田面积的平方来补贴每个农田。这是为了奖励那些边界清晰的农田。他们现在需要一个工具来计算这些多边形面积平方的总和,以确保补贴分配公平。

Generated from OpenStreetMap, ODBL 1.0

输入格式

第一行包含一个整数 $F$ ($3 \le F \le 1000$),表示栅栏线段的数量。接下来的 $F$ 行,每行包含四个整数 $x_1, y_1, x_2, y_2$ ($0 \le x_1, y_1, x_2, y_2 \le 1000$),表示一段直线栅栏。

任意两条栅栏线段不会相交。由于栅栏既昂贵又繁琐,你可以假设每一段栅栏都是必要的,并且都用于围成农田。农民拥有的所有栅栏都是连通的。

换句话说,由端点和栅栏组成的图是平面的、连通的,且没有桥。

输出格式

输出一行,表示由给定的栅栏部分所形成的所有农田的面积平方之和。如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$,则视为正确。

说明

图片展示了样例 2。两个农田的面积分别为 $1$ 和 $0.5$,因此它们面积的平方和为 $1 + 0.25 = 1.25$。

样例

样例输入 1

5
0 0 0 1
0 1 1 1
0 0 1 0
1 0 2 0
1 1 2 0

样例输出 1

2.25

样例输入 2

6
0 0 0 1
0 1 1 1
0 0 1 0
1 0 2 0
1 1 2 0
1 0 1 1

样例输出 2

1.25

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.