3750 - 油滴扩展
Description

在一张长方形的实验台上,最多可以选择 N 个位置各放置一个液滴。每个液滴会以圆形向四周均匀扩散,直到触碰到实验台的边界,或者触碰到此前已经放置好的液滴,此时它便不再继续扩散(不同的液滴之间不会融合)。

每次只能放置一个液滴,并且必须等当前液滴完全扩散结束后,才能放置下一个。请安排这 N 个位置的放置顺序,使得所有液滴完全扩散后,占据的总面积最大。

圆面积公式为 V = πr²,其中 r 为圆的半径。你只需要输出实验台剩余的最小空间(即实验台总面积减去液滴占据的最大面积),并将结果四舍五入为整数。

Input
  • 第一行一个整数 N。
  • 第二行为长方形一个顶点及其对角顶点的坐标 x1, y1, x2, y2。
  • 接下来 N 行,每行两个整数 x, y,表示实验台上第 i 个可放置液滴的位置。

当 N = 0 时,没有后续的坐标行。

Output

一行一个整数,表示实验台剩余的最小空间(四舍五入到整数)。

Examples

Input

2
0 0 10 10
3 3
7 7

Output

50

Input

1
332 -455 -346 -184
2 -423

Output

180521
Hint

本题使用标准输入输出(stdin/stdout),不需要写 freopen。

数据范围与约定

  • 对于 20% 的数据,0 ≤ N ≤ 1;
  • 对于 50% 的数据,0 ≤ N ≤ 3;
  • 对于 100% 的数据,0 ≤ N ≤ 6。
  • 所有坐标均为绝对值不超过 1000 的整数,长方形的面积为 |x2 − x1| × |y2 − y1|。
Source
CSP-J模拟赛7
Tags
题目参数
Time Limit 1 second
Memory Limit 256 MB
提交次数 2
通过次数 1