当前位置:首页 >> 学科竞赛 >>

计算几何专题


2013年ACM暑期集训
——计算几何专题

10级 赖鹏飞 浙江师范大学ACM集训队 2013.8.3

概述 ? 特点 –思考繁琐 –编程繁琐 –细节繁琐 ? 如何把握 – 需要在平时将计算几何的相关 子问题透彻研究 –模板的代码一定要规范 –赛场上重点想思路,不能将时间 花在纠缠细节上(否则finish egg?)

/>
需要注意的细节
(1)常用头文件#include<math.h> (2)计算几何中一般来说使用double型比较 频繁,请注意数据类型的选择,该用实数的时 候就用double,而float容易失去精度。 (3)判断double型的x是否为0,应当用x<eps && x>-eps(或者fabs(x)<eps),其中eps代 表某个精度,常常取eps=0.00000001,还有其 他类似情况也要注意double类型的精度问题, int(x+eps),避免x=4.999999999

需要注意的细节
(4)圆周率取3.141592654或者更精确,或者用 acos(-1.0)角度制和弧度制的转换,C/C++中的三角 函数均为弧度制 (5)尽量少用除法,开方,三角函数,容易失去精 度。用除法时注意除数不为0,输出的时候要小心0.00000,比如a=-0.0000001,printf(“%.5f”,a); (6)在使用反三角函数时,注意定义域的范围,如 acos(x),当x是你计算得到时可能会出现越界现象, 比如本来应该得到是1,而你计算得到谁 1.0000000001, 这时acos(x)的值就会出错了,所以我们可以加一 句判断,if(fabs(x-1)<eps||fabs(x+1)<eps) x=round(x)

专题训练: 必备知识:
向量及其运算、点线段直线、 三角形的性质、圆的相关计 算 多边形面积、凸包、多边 形重心、点在多边形内的 判定、正点多边形中的 Pick公式

例题讲解:
UVa 11178、UVALive 4757、 UVALive 4838、UVA 11168、 UVA 11796、POJ 1066

必备知识

向量及其运算
简单的说,向量(vector)就是有大小有方向的量,如速度、位 移等物理量都是向量。向量最基本的运算是加法、满足平行四边 形法则。

v

w+v

w

向量及其运算
在平面坐标系下,向量和点一样,也用两个数x、y表示。

struct Point //点的表示 { double x,y; //Point(double x=0,double y=0):x(x),y(y){} }; typedef Point Vector; //从程序实现上,Vector知识Point的别名

向量及其运算
向量基本运算的代码实现
Vector operator + (Vector A,Vector B) //向量+向量=向量 点+向量=点 { return Vector(A.x+B.x,A.y+B.y); } Vector operator - (Point A,Point B) //点-点=向量 { return Vector(A.x-B.x,A.y-B.y); } Vector operator * (Vector A,double p) //点*数=向量 { return Vector(A.x*p,A.y*p); }

向量及其运算
Vector operator / (Vector A,double p) //点/数=向量 { return Vector(A.x/p,A.y/p); } bool operator < (const Point &a,const Point &b) { return a.x<b.x||(a.x==b.x&&a.y<b.y); } int dcmp(double x) { if(fabs(x)<eps) return 0; else if(x<0) return -1; return 1; }

向量及其运算
bool operator == (const Point &a,const Point &b) //判断两点是否相等

{
return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0; } 注意到上面“相等”函数用到了“三态函数”dcmp,减少了精度问题。 另外,向量有一个所谓的极角,即从x轴正半轴旋转到该向量方向的角 度。C标准库里atan2函数是用来求极角的,如向量(x,y)的极角就 是atan2(y,x)(单位:弧度)。

向量及其运算
double Dot(Vector A,Vector B){ return A.x*B.x+A.y*B.y; } double Length(Vector A){ //模 //点积

return sqrt(Dot(A,A));
} double Angle(Vector A,Vector B){ //夹角

return acos(Dot(A,B)/Length(A)/Length(B)); }

向量及其运算
double Cross(Vector A,Vector B) { return A.x*B.y-A.y*B.x; } double Area2(Point A,Point B,Point C) { return Cross(B-A,C-A); } //叉积

//三角形面积两倍

Vector Rotate(Vector A,double rad) //向量逆时针旋转 { return Vector(A.x*cos(rad)A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad)); }

三角形的性质
外心:外接圆圆心,三条中垂线交点 内心:内接圆圆心,三条角平分线交点 重心:三条中线交点,注意其物理性质 垂心:三条垂线焦点
a b c ? ? 正弦公式:sin( A) sian( B) sin(C ) ? 2 R

余弦公式:cos( A) ?

b ?c ?a 2bc
2 2

2

C

b
D

a c
B

三角形的性质
中线公式: 高线: hA ?
mA ? 1 2(b 2 ? c 2 ) ? a 2 2

2 a?b?c p( p ? a)( p ? b)( P ? c) , ( p ? ) a 2
2 b?c bcp ( p ? a )

角平分线公式:t A ?

面积(海伦公式): S ?

p ( p ? a )( p ? b)( p ? c)
C

abc 外接圆半径: R ? 4S

b
D

a c
B

三角形的性质
S 内接圆半径: r ? p
广义勾股定理:

c ? a ? b ? 2 BC * DC
2 2 2

注:海伦公式推广到四边形 婆罗摩笈多公式:

S ? p( p ? a)( p ? b)( p ? c)( p ? d )
C

b
D

a c
B

点、线段、直线

1.直线的参数表示
直线可以用直线上的一个点P0和方向向量v表 示,直线所有的点P=P0+vt,其中t为参数。

已知直线上面的两点A、B,则可表示直线方 程为A+(A-B)t。
优点:可以表示所有直线; 可以通过限制参数来表示线段和射线

点、线段、直线

2.相交直线交点
设直线方程分别为P+vt和Q+wt,设向量u=QP,交 点在第一条直线的参数t1,第一条直线的参数t2, 怎x和y坐标可列出一个方程,解得:

cross( w, u ) t1 ? , cross(v, w)

cross(v, u ) t2 ? cross(v, w)

点、线段、直线
Point GetLineIntersection(Point P,Vector v,Point Q,Vector w) { //两直线交点,点、向量表示直线 Vector u=P-Q; double t=Cross(w,u)/Cross(v,w); return P+v*t; }

注:从上述公式可得,当P,v,Q,w各分量为有理数的时候, 交点坐标也为有理数,当精度要求极高的情况下,可以考虑用 自定义分数类;

点、线段、直线

2.点到直线的距离
点到直线的距离是很常用的函数,可用叉积计算的到,及用平行 四边形的面积除以底。代码如下: double DistanceToLine(Point P,Point A,Point B)//点到直线距离 { Vector v1=B-A,v2=P-A; return fabs(Cross(v1,v2)/Length(v1)); }

点、线段、直线

3.点到线段的距离
double DistanceToSegment(Point P,Point A,Point B) { if(A==B) return Length(P-A); Vector v1=B-A,v2=P-A,v3=P-B; if(dcmp(Dot(v1,v2))<0) return Length(v2);

else if(dcmp(Dot(v1,v3))>0) return Length(v3);
else return fabs(Cross(v1,v2)/Length(v1)); }

点、线段、直线

4.线段相交判定
我们定义“规范相交”为两条线段恰有一 个交点,丏丌在任何一条线段的端点。每

一条线段的两个端点都在另一条线段的两 侧,可以用叉积的符号来判断;

点、线段、直线
bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2) {

//线段相交判定(规范相交)
double c1=Cross(a2-a1,b1-a1); double c2=Cross(a2-a1,b2-a1);

double c3=Cross(b2-b1,a1-b1);
double c4=Cross(b2-b1,a2-b1); return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;

}

点、线段、直线
丌规范相交时再判断端点的情况就好:

bool OnSegment(Point p,Point a1,Point a2)
{ //点不线段判定 return dcmp(Cross(a1-p,a2p)==0&&dcmp(Dot(a1-p,a2-p))<0);

}

圆的相关计算
(一)直线与圆的交点
假定直线为AB,圆的圆心为C,半径为r。 方法一:解方程 联立直线方程和圆方程,得到二次函数,可通过二次函 数的求解得到直线和圆的关系及其交点坐标。 方法二:几何法 求C在AB上的投影p,再求AB对应的单位向量v;则两 交点为p-Lv和p+Lv,L为p到交点的距离,在通过勾股定理即可 求得结果。

圆的相关计算
(二)两圆相交

圆的相关计算
/*HDU 1798 两圆相交面积*/ #define PI acos(-1.0) int main(){ double a1,b1,r1,a2,b2,r2,d; double A1,A2,s1,s2,s; while(~scanf("%lf%lf%lf%lf%lf%lf",&a1,&b1,&r1,&a2,&b2, &r2)){ d=sqrt((a2-a1)*(a2-a1)+(b2-b1)*(b2-b1)); //求圆心距 if(d>=r1+r2) printf("0.000\n"); //两圆相离或相外



圆的相关计算
else if(d<=fabs(r1-r2) && d>=0) { //内切 if(r1>r2) printf("%0.3lf\n",PI*r2*r2); else printf("%0.3lf\n",PI*r1*r1); } else{ A1=2*acos((d*d+r1*r1-r2*r2)/(2*d*r1)); //求以圆心为顶点与 两圆交点连线的角 A2=2*acos((d*d+r2*r2-r1*r1)/(2*d*r2)); s1=0.5*r1*r1*sin(A1)+0.5*r2*r2*sin(A2); s2=A1/2*r1*r1+A2/2*r2*r2; s=s2-s1; printf("%0.3lf\n",s); } } }

HDU 1798 Tell me the area(两圆相交面积) POJ 1269 Intersecting Lines(两直线关系) POJ 1118 Lining Up(最多共线点数) POJ 3304 Segments(直线与线段关系) HDU 1071 The area(抛物线与直线所围面积) HDU 2105 The Center of Gravity(三角形重心) UVALive 5827 Regular Convex Polygon(三角形外心) POJ 4048 Chinese Repeating Crossbow(射线与线段关系) POJ 1410 Intersection(线段与矩形关系) POJ 2398 Toy Storage(点与直线关系)

来试一试嘛

与题训练

多边形面积 基本问题(1):
给定一个简单多边形,求其面积。 输入:多边形(顶点按逆时针顺序排列)

输出:面积S

Any good idea?

多边形面积 三角形的面积:
在解析几何里, △ABC的面积可以通过如下方法求得: 点坐标 => 边长 => 海伦公式 => 面积 缺点:
计算量大 精度损失

多边形面积 计算几何的方法:
在计算几何里,我们知道,△ABC的面积就是“向

量AB”和“向量AC”两个向量叉积的绝对值的一半。
其正负表示三角形顶点是在右手系还是左手系。
B C A ABC成左手系,负面积 A ABC成右手系,正面积 C B

多边形面积
Area(A,B,C)= 1/2 * (↑AB) × (↑AC)

=∣

Xb – X a Xc – X a

Yb –Y a Yc –Y a

∣/2

特别注意: 以上得到是有向面积(有正负)!

多边形面积 凸多边形的三角形剖分
很自然地,我们会想到以 P1为扇面中心,连接P1Pi就 得到N-2个三角形,由亍凸性,保证这些三角形全在多

边形内,那么,这个凸多边形的有向面积:
A=sigma(Ai) (i=1…N-2)
P6 P1 A4 P5 A3 A1 P2 A2 P3 P4

多边形面积

凹多边形的面积
P3

P4

P2

P1

多边形面积

任意点为扇心的三角形剖分:
我们能把多边形分成N-2个三角形,为什么不能分成 N个三角形呢? 比如,以多边形内部的一个点为扇心,就可以把多边 形剖分成 N个三角形。
P3 P2 P4 P1 P5 P6

多边形面积 前面的三角剖分显然对于多边形内部任意一点

都是合适的!(把分割点放在原点?)
我们可以得到:A=sigma(Ai) ( i=1…N )

即:

A= sigma∣

Xi – X0 X(i+1) – X0

Yi –Y0

Y(i+1) –Y0

∣/2

( i=1…N )

点在多边形内的判定
方法一:射线法 从判定点任意引一条射线,如果和边 界的交点是奇数次,说明点在多边形内,如 果交点为偶数个,点在多边形外。在多边形 上需另外判断。 方法二:转角法 计算多边形每条边的转角的和,如果 为360度,则点在多边形内,如果为0度,则 在多边形外,如果为180度则点在多边形上 (也适合非简单多边形)。

点在多边形内的判定
如果按照上面的定义实现,需要计算大量 的反三角函数,不仅速度慢,而且容易产生精度 误差。我们一般假设一条向右的射线,统计多边 形穿过这条射线的正反次数,把这个数记为绕数 wn(Winging Number),逆时针穿过是wn++, 顺时针穿过wn--。 注意在程序现实的时候,判断是否穿过, 以及穿过方向时,需要用叉积判断输入点在边的 左边还是右边。

点在多边形内的判定
int isPointInPolygon(Point p,Polyon poly) { int w=0,n=v.size(); for(int i=0;i<n;i++) { //在边上 if(isPointOnSegment(p,poly[i],poly[(i+1)%n])) return -1; int k=dcmp(Cross(poly[(i+1)%n]-poly[i],p-poiy[i])); int d1=dcmp(poly[i].y-p.y); int d2=dcmp(poly[(i+1)%n].y-p.y); if(k>0&&d1<=0&&d2>0) wn++; if(k<0&&d2<=0&&d1>0) wn--; } if(wn!=0) return 1;//内部 return 0; //外部 }

凸包

顾名思义,凸包就是把给定点包围在内部、 面积最小的图多边形,它在计算几何里有着

极其重要的作用。

凸包
在网上可以找到很多关于凸包的算法的资料, 这里我们简单叙述一下基于水平序的Andrew 算法。
首先把所有的点按照x从小到大排列(x相同, 按y从小到大排列),删除重复点得到序列p1, p2,……,然后把p1,p2放到凸包中,从p3 开始,当新点在凸包“前进”方向的左边时 继续前进,否则依次删除最近加入凸包的点, 直到新点在左边。

凸包
如图,新点p18在向量p10p15(即当前前进方向)的右边, 因此需要从凸包上删除p15和p10,让p8的下一个点为p18。 重复上述过程,直到碰到最右边的点pn,就求得了“下凸 包”。然后反过来从pn开始再做一遍,求出“上凸包”,合 并起来就是完整的凸包了。
p15

p15

p10 p5 p8

p18

p10

p18

p5
p8

凸包
int ConvexHull(Point* p,int n,Point* ch) { sort(p,p+n); int m=0; for(int i=0;i<n;i++) { while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-1])<=0) m--; ch[m++]=p[i]; } int k=m; for(int i=n-1;i>=0;i--) { while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-1])<=0) m--; ch[m++]=p[i]; } if(n) m--; return m; }

多边形的重心

给定一个简单多边形,求其重心。

输入:多边形(顶点按逆时针顺序 排列) 输出:重心点C

多边形的重心

从三角形的重心谈起:
三角形的重心是: (x1+x2+x3) / 3,(y1+y2+y3) / 3 可以推广否? Sigma(xi)/N , sigma(yi)/N (i=1…N) ???

多边形的重心

看看一个特例:

多边形的重心

原因:
错误的推广公式是“质点系重心公式”,即如 果认为多边形的质量仅分布在其顶点上,丏均 匀分布,则这个公式是对的。 但是,现在多边形的质量是均匀分布在其内部 区域上的,也就是说,是不面积有关的!

多边形的重心

Solution:
剖分成N个三角形,分别求出其重心和面积, 这时可以想象,原来质量均匀分布在内部区域 上,而现在质量仅仅分布在这N个重心点上 (等假变换),这时候就可以利用刚才的质点 系重心公式了。 不过,要稍微改一改,改成加权平均数,因为 质量不是均匀分布的,每个质点代表其所在三 角形,其质量就是该三角形的面积(有向面 积!),——这就是权!

正点多边形中的Pick公式

问题描述:
给出一个正点多边形(格点多边形),求多边形的 面积,以为多边形内部的格点数目和多边形边上的 格点数目 。

正点多边形中的Pick公式

pick公式:
多边形的面积=多边形边上的格点数目/2+多边形内 部的格点数目-1 对于每一条线段来说,如果是水平或者垂直,显然 可以得到,否则则是坐标差的最大公约数加1.

全部 搞定 !
UVA 12304 2D Geometry 110 in 1! (综合) POJ 1113 Wall(凸包周长) POJ 3348 Cows(凸包面积) POJ 1265 Area(简单格点多边形) UVA 10652 Board Wrapping (凸包)

例题分析

UVa 11178 Morley's Theorem

题目意思:Morley定理是这样的:做三角
形ABC每个内角的三等分线,相交成三角形DEF, 则DEF是等边三角形,如图所示。 你的任务就是根据给定的A、B、C3个点的坐标 来确定D、E、F的坐标。其中A、B、C按照逆时 针顺序排列。

UVa 11178 Morley's Theorem 这题应该说很简单,在你看来,怎么解 决? 以D点为例,D是BD,CD的交点,BD 可由BC逆时针旋转三分之一∠ABC得 到,同理可得到CD,然后求两直线交 点即可。

UVALive 4757 Open-air shopping malls

题目意思:平面上有n个圆,给定他
们各自的圆心和半 径。保证任意两个圆 不会互相重叠。现在 求一个大圆,它的 圆心与某个给定圆的圆心重合,且对于每 一个给定的圆,大圆至 少覆盖该圆面积 的一半。请求得满足要求 的大圆的最小 半径。

UVALive 4757 Open-air shopping malls 困难问题:直接求满足要求的最小半径 简单问题:已知一个半径,要判断它是 否覆盖了给定圆的至少一半面积 性质:当圆心确定,若半径r的圆可以 覆盖每一个给定圆至少一半的面积,那 么对于半径R>r的圆,都可以覆盖至少 一半的面积。 算法:二分答案

UVALive 4757 Open-air shopping malls 求两圆的相交面积 :

UVALive 4757 Open-air shopping malls 算法流程 –枚举圆心位置Oi –二分查找,求得对于当前圆心位置, 满足要求的最小半径ri –记录上述所有r 中的最小值,并且输 出结果。 时间复杂度 –O(n2logn)

UVALive 4838 Rotational Painting

题目意思:有一块均匀厚度的多边
形玻璃板,现在需要将它稳定地竖直放 置,求有多少种不同的放置方法。题目 描述中的图1和图2分别表示两个多边形 的所有放置 方法,而图3 中的两种放法 我们认为是不稳定的。

UVALive 4838 Rotational Painting

UVALive 4838 Rotational Painting “稳定”的定义 – 多边形玻璃板的重心向水平面作垂 线时,垂足落在支撑边所在的线段上 (不包括线段端点) 对多边形支撑边的枚举 – 由于有可能出现凹多边形,因此可 供选择的 “支撑边”包括该多边形的凸 包的所有边。

UVALive 4838 Rotational Painting 重心的求法 –有向质量(回顾有向面积) 重心的求法 –对于三顶点坐标为(x1,y1)、(x2,y2)及 (x3,y3) 的三角形,其重心公式为: ? x0=(x1+x2+x3)/3 ? y0=(y1+y2+y3)/3 – 多边形三角剖分 ? 有向面积作为质量 (有向质量)

UVALive 4838 Rotational Painting 总结 –求出多边形凸包; –求出多边形重心坐标; – 由重心向每一条凸包边所在直线引 垂线,通过垂足的位置判断该凸包边能 否作为支撑边。并 在枚举过程中统计符 合条件的支撑边(即摆放方法)的个数。

UVA 11168 Airport

题目意思:给出平面上n
(n≤10000)个点,找一条直线,是的 所有的点都在直线的同侧(也可以在直 线上),且使得各个点到直线的距离的 和尽量小。

UVA 11168 Airport 怎么来枚举直线? 直线不可以穿过所有点组成的凸包,不 难发现,选择凸包边所在的直线要比选 择和凸包相离的直线更划算。 最直接的想法,枚举直线,再统计其他 点到到该直线的距离,时间复杂度o(n2)。 显然这个比现实。那怎么优化?

UVA 11168 Airport 点到直线的距离公式: D ? Ax0 ? By0 ? C
A2 ? B 2

注意:所有的点都在直线的同一侧,我们 可以由线性规划的知识得到,Ax+By+C 的正负号是一致的,所以我们就可以将公 n ?1 n ?1 式化解为: A? xi ? B ? yi ?nc n ?1 Axi ? Byi ? C i ?0 sum( D ) ? ? ? i ?0 2 2 2 2 i ?0
A ?B A ?B

所以只要预处理出所有x坐标的和y坐标之 和,就可以在o(1)时间总距离。

UVA 11796 Dog Distance

题目意思:甲和乙两条狗分别沿着
一条折线的路径奔跑,两只狗的速度未 知,但他们同时出发,同时到达终点, 并且都是匀速奔跑。你的任务就是求出 甲和乙在奔跑过程中最远距离和最近距 离之差。

UVA 11796 Dog Distance 两个都是在动态变化的,这个看起了很 难处理,怎么办? 简单例子:甲和乙的运动就是一条线段, 那我们怎么处理? 由运动的相对性,我们可以假设甲是不 动的,只有乙在运动,这样我们可以把 他转化为: ——点到线段的距离

UVA 11796 Dog Distance 有了简化版的分析,只需模拟整个过程就 好。怎么模拟? ——假设现在甲的位置在pa,刚经过编号 为sa的拐点;乙的位置在pb,刚记过编号 为sb的拐点,则我们只需要计算他俩谁先 到达下一个观点就好,那么在这个时间点 之前的问题就是我们刚才讨论过的“简化 版”。求解完毕后更新最值,正好到达下 一个拐点的时候还要更新sa和/或sb,然 后继续模拟,时间复杂度o(n+m)。

HDU 4533 威威猫系列故事——晒被子

题目意思:在第一象限有n个平行
于坐标轴的矩形被子,不同的被子可能 有部分重叠,然后有q次询问,每次输 入一个t,表示在(0,0)到(t,t)被 水淹了,问你被子湿了的总面积是多少。 数据范围:
0 < N <= 20000 1 <= x1 < x2 <= 200000 1 <= y1 < y2 <= 200000 1 <= x <= 20000 1 <= ti <= 200000 (1 <= i <= x )

HDU 4533 威威猫系列故事——晒被子 看到题目,你的想法是?

对于这题的直接想法,也是最暴力的想 法就是对于每一次询问都是算一遍,显 然时间是不允许的!那怎么办,有没有 高效的算法来实现呢?

HDU 4533 威威猫系列故事——晒被子 考虑每次询问t,对于单一矩形的面积的 计算方法~ 情况一:
计算如图矩形所被包含 的面积可以用矩形面积 S[TCFI]-S[TJGI],而 S[TCFI]=(t-Fx)*(t-Fy); S[TJGI]=(t-Gx)*(t-Gy) 换句话说就是用[T和矩 形左下角的点形成的面 积]减去[T和矩形右下角 形成的矩形面积]就是这 个矩形被包含的面积!

HDU 4533 威威猫系列故事——晒被子 情况二: 当前矩形被包涵 的面积是 S[TLFI]-S[TLEK]。 即[T和矩形左下 角点形成的面积] 减去[T和矩形左 上角点形成的矩 形的面积]!

HDU 4533 威威猫系列故事——晒被子 情况三:
这时候的面积是EHGF的面 积,但我们还想计算这个面 积时和T有关。仿照前面的 讨论,发现S[EHGF]不就是 S[TLFI]-S[TLEN]S[TMGI]+S[TMHN]么? 换句话描述,就是[T和矩形 左下角点形成的矩形面积] 减去[T和矩形左上角点形成 的矩形面积]减去[T和矩形 右下角点形成的矩形面积] 加上[T和矩形右上角点形成 的矩形面积]

HDU 4533 威威猫系列故事——晒被子
那么我们得到了如下算法: 输入询问t sum=0 遍历所有矩形的四个顶点 如果该顶点在(0,0)-(t,t)的范围内 如果当前顶点是它所在矩形的左上角或右下 角的点那么sum+=[(t,t)和该点形成的矩形的面积] 否则sum-=[(t,t)和该点形成的矩形的面积] 返回sum

HDU 4533 威威猫系列故事——晒被子

对于这题目的数据来说时间复杂度肯定是 不够的,我们要想办法优化它。。。
观察我们计算[T和当前点形成的矩形面 积]时的方法: 假设当前点坐标是(x,y) 那么S=(t-x)*(t-y) 我们可以将上式展开:S=t*t-t(x+y)+xy 我们可不可以将上式分成的三部分分别 求和呢?答案是可以的!

HDU 4533 威威猫系列故事——晒被子

那么我们可以将所有矩形左下角和右上角 的点分到一组a(因为它们和T形成的矩 形面积都是做“加”运算),把左上角和 右下角的点分到一组b(因为它们和T形 成的矩形面积都是做“减”运算)
那么结果可以写成sigma[a中在(t,t)范围 内的点和T形成的矩形面积]-sigma[b在 (t,t)范围内的点和T形成的矩形面积]

HDU 4533 威威猫系列故事——晒被子

我们将a,b中的点分别按max(x,y)排序。
对于每次询问t,我们二分找到它在a,b中 的位置n,m(即max(x,y)恰好不超过t的 最大的下标,a,b都是从1开始编号)
答案不就是 Sum(Sa)-Sum(Sb) =sigma[t*t-t*(x+y)+xy]-sigma[t*t-t*(x+y)+xy] =[sigma(t*t)-sigma(x+y)+sigma(xy)]-[sigma(t*t)sigma(x+y)+sigma(xy)]

HDU 4533 威威猫系列故事——晒被子
总结: (1)检查所有矩形的四个顶点,如果是左下角或是右上 角的点那么放到a的末尾,否则放到b的末尾。 (2)将a,b中的所有点按max(x,y)排序 (3)定义suma,sumb表示a、b的点中下标1到下标i的所 有点的x+y和定义suma_mul,sumb_mul表示a、b的点中下 标1到下标i的所有点的x*y和,循环 i=1 到 2*N suma[i]=suma[i-1]+a[i].x+a[i].y sumb[i]=sumb[i-1]+b[i].x+b[i].y suma_mul[i]=suma_mul[i-1]+a[i].x*a[i].y sumb_mul[i]=sumb_mul[i-1]+b[i].y*b[i].y (4)对于每次询问t,二分找到在a,b中max(x,y)恰好不超 过t的下标n,m,输出答案(t*t*n-t*suma[n]+suma_mum[n])(t*t*m-t*sumb[m]+sumb_mul[m])

POJ 1066 Treasure Hunt

题目意思:
一个正方形围墙 内有一些交错的 内墙,内墙的端 点都在正方形上, 在正方形内部有 一个点,求从正 方形外到这个点 的最少要走的门 数,门只能是线 段的中点。

POJ 1066 Treasure Hunt 看似相当的复杂,你的着手点在哪里? 从一个点到终点不可能“绕过”围墙, 只能穿过去,所以门是否开在中点是无 所谓的,只要求四周线段中点到终点的 线段与墙的最少交点个数即可。 更进一步,实际上,只需判断四周围墙 的所有点与终点的连线与内墙的最少交 点加一即可

课堂寄语

有志者自有千计万计, 无志者只感千难万难。


相关文章:
几何计算专题
几何计算专题_初三数学_数学_初中教育_教育专区。几何计算专题 姓名 班级 1.①已知等腰三角形的两边长为 4cm,3cm,则这个等腰三角形的周长是 cm. ②已知等腰三角...
ACM_计算几何类题目
五。计算几何背景,实际上解题的关键是其他问题(数据结构、组合 数学,或者是枚举思想) 若干道经典的离散化+扫描线的题目,ACM 选手必做题目 POJ 1151 Atlantis (...
计算几何复习题
计算几何复习题_计算机软件及应用_IT/计算机_专业资料。计算几何期末复习题 二. 简答题 1. 在编写几何计算程序时,应该坚持的原则有哪些? 答:尽量使用加减等有理...
acm计算几何资料
计算几何专题 63页 免费 ACM计算几何题目总结及分... 6页 免费 ACM必做50题...计算几何资料一,引言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化,...
几何计算专题
几何计算专题_初三数学_数学_初中教育_教育专区。中考几何计算专题 例1:问题背景 在某次活动课中,甲、乙、丙三个学习小组于同一时刻在阳光 : 下对校园中一些...
专题1 几何计算专题
中考系列复习——几何计算专题一、中考要求 证明与计算,是几何命题的两大核心内容。几何计算题,通常需要借助几何中的概念、 定义、定理、公理等知识,求解相关几何元素...
ACM计算几何题目总结及分类
ACM计算几何题目总结及分类_数学_高中教育_教育专区。ACM计算几何题目总结及分类 ...计算几何专题 63页 免费 acm计算几何资料 17页 免费 计算几何 36页 免费 ...
0专题1 几何计算专题
中考系列复习——几何计算专题一,中考要求 证明与计算,是几何命题的两大核心内容.几何计算题,通常需要借助几何中的概念, 定义,定理,公理等知识,求解相关几何元素的...
上海市2011学年各区几何计算专题
上海市2011学年各区几何计算专题_初三数学_数学_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档上海市2011学年各区几何计算专题_初三数学_数学_初中教育_...
几何计算专题训练
几何计算专题训练_数学_小学教育_教育专区。几何计算专题训练 1、如图,已知圆锥的高为 4,底面圆的直径为 6,则此圆锥的侧面积是( A. 12π B. 15π C. 24...
更多相关标签:
高三立体几何专题 | 初二几何专题训练 | 高考数学立体几何专题 | 小学奥数几何专题 | 平面解析几何专题 | 高考立体几何专题 | 高中数学解析几何专题 | 立体几何专题 |