问题 1554 --雪花

1554: 雪花

时间限制: 1 Sec  内存限制: 128 MB
提交: 49  解决: 20
[提交][状态][讨论版][命题人:]

题目描述

终于放假了!SPFA太闲了,在家看雪花。

有几粒雪花落到了窗户上。窗户是个矩形,当雪花落到窗户上,它会融化成水,接着变成一个规则的圆,半径不断变大,直到这个圆碰到窗户的边框或其他圆为止。

雪花会依次落到窗户上,且每片雪花都必须等其它圆扩展完才能落下。

   为了计算方便,可以把窗户和雪花的位置看成是平面之间坐标系中的点。

给出窗户的位置以及每个圆的坐标。SPFA想知道,以什么样的顺序使雪花落下,能使覆盖窗户的面积最大。

输入

第一行输入四个实数,x1,y1,x2,y2,窗户左上角的坐标和窗户右下角的坐标。

第二行输入n,雪花的片数。

接着输入n行,每行两个实数xi和yi,每片雪花的坐标。

输出

输出1行,一个整数,窗户剩余的没有被覆盖的最小面积(对结果四舍五入)

样例输入

10 10 20 0
2
13 3
17 7

样例输出

50

提示


圆周率:3.14.5926



对于10%的数据,n=1;



对于20%的数据,n<=2;



对于60%的数据,n<=4;



对于100%的数据,n<=6,-1000<=x1,y1,y2,y2,xi,yi<=1000;

来源

[提交][状态]