![](/skins/sea/images/title_post.gif)
2009年6月29日
这道题灵活的考察了凸包的性质,是Graham算法的变形,要求的是永不右转的最长路径,其实题目中最大的数量一定是n,这很容易想到,相当于一圈圈的剥洋葱一样,每次取最外面的点,总能取遍所有的点。
我的算法也是这样设计的,每一次都是找凸包,找完当前的凸包以后,以最后一个点为始点,重新按极角排序后再找,直到所有的点都被找遍为止。
这题比较麻烦,模板改动也比较多,要理解几个函数的含义才能做得出来,下面是我的实现代码:
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define eps 1e-8
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct Point{int x,y,k;};
Point pt[61], stk[61];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int Xmult(Point p1,Point p2,Point p0){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
Point p1,p2;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int graham_cp(const void* a,const void* b){
int ret=Xmult(*((Point*)a),*((Point*)b),p1);
return (ret==0)?(Xmult(*((Point*)a),*((Point*)b),p2)>0?-1:1):(ret>0?-1:1);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void ASort( int n, Point* pt ){
int i,k=0;
for (p1=p2=pt[0],i=1;i<n;p2.x+=pt[i].x,p2.y+=pt[i].y,i++)
if (p1.y-pt[i].y>eps||((p1.y-pt[i].y==0)&&p1.x>pt[i].x))
p1=pt[k=i];
p2.x/=n,p2.y/=n;
pt[k]=pt[0],pt[0]=p1;
qsort(pt+1,n-1,sizeof(Point),graham_cp);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main(){
int t, n, m, i, j, cnt;
scanf("%d",&t);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while( t-- ){
scanf("%d",&n);
for( i= 0; i< n; i++ ) scanf("%d%d%d",&pt[i].k,&pt[i].x,&pt[i].y);
cnt= 0, m= n;
ASort(m,pt);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while( cnt< n ){
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for( stk[cnt++]=pt[0],stk[cnt++]=pt[1],stk[cnt++]=pt[2],i=3,j=1; i< m; i++ ){
for( ;cnt>2&&Xmult(stk[cnt-2],pt[i],stk[cnt-1])>=0; pt[j++]=stk[--cnt] );
stk[cnt++]=pt[i];
}
pt[0]= stk[--cnt], m= j;
qsort(pt+1,m-1,sizeof(Point),graham_cp);
}
printf("%d",n);
for( i= 0; i< n; i++ )
printf(" %d",stk[i].k);
putchar('\n');
}
return 0;
}
posted @
2009-06-29 20:49 古月残辉 阅读(774) |
评论 (0) |
编辑 收藏
这两题几乎是一样的,都是求给定半径的圆能覆盖的最多点的个数。我想的方法是O(n^3)的,时间用的比较多……
思路是枚举两两点,根据它们的坐标和半径求出圆心的坐标,再判断所有点是否在圆内,题目不难,公式较繁,细心点就行了,还有要注意至少能选一个点,以及斜率不存在等等边界的情况,我就wa了很多次……
时间的话,有O(n^2lgn)的,网上搜到,看了下,是把每个点作为圆心,再求每个圆与其它圆的交,记录交点,再经过处理就可以得到在同一个圆内的点数,感觉也蛮繁的,就没去实现了……有兴趣自已搜,至于那些个100ms的大牛们什么思路,我也就不得得知了……
posted @
2009-06-29 16:28 古月残辉 阅读(995) |
评论 (0) |
编辑 收藏
原来在文章里转的,现在放到计算几何专题中来:
计算几何题的特点与做题要领:
1.大部分不会很难,少部分题目思路很巧妙
2.做计算几何题目,模板很重要,模板必须高度可靠。
3.要注意代码的组织,因为计算几何的题目很容易上两百行代码,里面大部分是模板。如果代码一片混乱,那么会严重影响做题正确率。
4.注意精度控制。
5.能用整数的地方尽量用整数,要想到扩大数据的方法(扩大一倍,或扩大sqrt2)。因为整数不用考虑浮点误差,而且运算比浮点快。
一。点,线,面,形基本关系,点积叉积的理解
POJ 2318 TOYS(推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2318
POJ 2398 Toy Storage(推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2398
一个矩形,有被若干直线分成N个格子,给出一个点的坐标,问你该点位于哪个点中。
知识点:其实就是点在凸四边形内的判断,若利用叉积的性质,可以二分求解。
POJ 3304 Segments
http://acm.pku.edu.cn/JudgeOnline/problem?id=3304
知识点:线段与直线相交,注意枚举时重合点的处理
POJ 1269 Intersecting Lines
http://acm.pku.edu.cn/JudgeOnline/problem?id=1269
知识点:直线相交判断,求相交交点
POJ 1556 The Doors (推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1556
知识点:简单图论+简单计算几何,先求线段相交,然后再用Dij求最短路。
POJ 2653 Pick-up sticks
http://acm.pku.edu.cn/JudgeOnline/problem?id=2653
知识点:还是线段相交判断
POJ 1066 Treasure Hunt
http://acm.pku.edu.cn/JudgeOnline/problem?id=1066
知识点:线段相交判断,不过必须先理解“走最少的门”是怎么一回事。
POJ 1410 Intersection
http://acm.pku.edu.cn/JudgeOnline/problem?id=1410
知识点:线段与矩形相交。正确理解题意中相交的定义。
详见:http://hi.baidu.com/novosbirsk/blog/item/68c682c67e8d1f1d9d163df0.html
POJ 1696 Space Ant (推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1696
德黑兰赛区的好题目。需要理解点积叉积的性质
POJ 3347 Kadj Squares
http://acm.pku.edu.cn/JudgeOnline/problem?id=3347
本人的方法极度猥琐。复杂的线段相交问题。这个题目是计算几何的扩大数据运算的典型应用,扩大根号2倍之后就避免了小数。
POJ 2826 An Easy Problem?! (推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2826
问:两条直线组成一个图形,能容纳多少雨水。很不简单的Easy Problem,要考虑所有情况。你不看discuss看看能否AC。(本人基本不能)提示一下,水是从天空垂直落下的。
POJ 1039 Pipe
http://acm.pku.edu.cn/JudgeOnline/problem?id=1039
又是线段与直线相交的判断,再加上枚举的思想即可。
POJ 3449 Geometric Shapes
http://acm.pku.edu.cn/JudgeOnline/problem?id=3449
判断几何体是否相交,不过输入输出很恶心。
此外,还有一个知识点,就是给出一个正方形(边不与轴平行)的两个对角线上的顶点,需要你求出另外两个点。必须掌握其方法。
POJ 1584 A Round Peg in a Ground Hole
http://acm.pku.edu.cn/JudgeOnline/problem?id=1584
知识点:点到直线距离,圆与多边形相交,多边形是否为凸
POJ 2074 Line of Sight (推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2074
与视线问题的解法,关键是求过两点的直线方程,以及直线与线段的交点。数据有一个trick,要小心。
二。凸包问题
POJ 1113 Wall
http://acm.pku.edu.cn/JudgeOnline/problem?id=1113
知识点:赤裸裸的凸包问题,凸包周长加上圆周。
POJ 2007 Scrambled Polygon
http://acm.pku.edu.cn/JudgeOnline/problem?id=2007
知识点:凸包,按极角序输出方案
POJ 1873 The Fortified Forest (推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1873
World Final的水题,先求凸包,然后再搜索。由于规模不大,可以使用位运算枚举。
详见:http://hi.baidu.com/novosbirsk/blog/item/333abd54c7f22c52574e0067.html
POJ 1228 Grandpa's Estate (推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1228
求凸包顶点数目,很多人求凸包的模板是会多出点的,虽然求面积时能得到正确答案,但是在这个题目就会出问题。此外,还要正确理解凸包的性质。
POJ 3348 Cows
http://acm.pku.edu.cn/JudgeOnline/problem?id=3348
凸包面积计算
三。面积问题,公式问题
POJ 1654 Area
http://acm.pku.edu.cn/JudgeOnline/problem?id=1654
知识点:利用有向面积(叉积)计算多边形面积
POJ 1265 Area
http://acm.pku.edu.cn/JudgeOnline/problem?id=1265
POJ 2954 Triangle
http://acm.pku.edu.cn/JudgeOnline/problem?id=2954
Pick公式的应用,多边形与整点的关系。(存在一个GCD的关系,即在两点(x1,y1),(x2,y2)连线之间的整点个数(包含一个端点)为:gcd(|x1-x2|,|y1-y2|);)
四。半平面交
半平面交的主要应用是判断多边形是否存在核,还可以解决一些与线性方程组可行区域相关的问题(就是高中时的那些)。
POJ 3335 Rotating Scoreboard
http://acm.pku.edu.cn/JudgeOnline/problem?id=3335
POJ 3130 How I Mathematician Wonder What You Are!
http://acm.pku.edu.cn/JudgeOnline/problem?id=3130
POJ 1474 Video Surveillance
http://acm.pku.edu.cn/JudgeOnline/problem?id=1474
知识点:半平面交求多边形的核,存在性判断
POJ 1279 Art Gallery
http://acm.pku.edu.cn/JudgeOnline/problem?id=1279
半平面交求多边形的核,求核的面积
POJ 3525 Most Distant Point from the Sea (推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3525
给出一个多边形,求里面的一个点,其距离离多边形的边界最远,也就是多边形中最大半径圆。
可以使用半平面交+二分法解。二分这个距离,边向内逼近,直到达到精度。
POJ 3384 Feng Shui (推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3384
半平面交实际应用,用两个圆覆盖一个多边形,问最多能覆盖多边形的面积。
解法:用半平面交将多边形的每条边一起向“内”推进R,得到新的多边形,然后求多边形的最远两点。
POJ 1755 Triathlon (推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1755
半平面交判断不等式是否有解。注意不等式在转化时正负号的选择,这直接影响到半平面交的方向。
POJ 2540 Hotter Colder
http://acm.pku.edu.cn/JudgeOnline/problem?id=2540
半平面交求线性规划可行区域的面积。
POJ 2451 Uyuw's Concert
http://acm.pku.edu.cn/JudgeOnline/problem?id=2451
Zzy专为他那篇nlogn算法解决半平面交问题的论文而出的题目。
五。计算几何背景,实际上解题的关键是其他问题(数据结构、组合数学,或者是枚举思想)
若干道经典的离散化+扫描线的题目,ACM选手必做题目
POJ 1151 Atlantis (推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1151
POJ 1389 Area of Simple Polygons
http://acm.pku.edu.cn/JudgeOnline/problem?id=1389
矩形离散化,线段树处理,矩形面积求交
POJ 1177 Picture (推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1177
矩形离散化,线段树处理,矩形交的周长,这个题目的数据比较强。线段树必须高效。
POJ 3565 Ants (推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3565
计算几何中的调整思想,有点像排序。要用到线段相交的判断。
详见:http://hi.baidu.com/novosbirsk/blog/item/fb668cf0f362bec47931aae2.html
POJ 3695 Rectangles
http://acm.pku.edu.cn/JudgeOnline/problem?id=3695
又是矩形交的面积,但是由于是多次查询,而且矩形不多,使用组合数学中的容斥原理解决之最适合。线段树是通法,但是除了线段树,还有其他可行的方法。
POJ 2002 Squares
http://acm.pku.edu.cn/JudgeOnline/problem?id=2002
枚举思想,求平面上若干个点最多能组成多少个正方形,点的Hash
POJ 1434 Fill the Cisterns!(推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1434
一开始发昏了,准备弄个线段树。其实只是个简单的二分。
六。随机算法
POJ 2420 A Star not a Tree?
http://acm.pku.edu.cn/JudgeOnline/problem?id=2420
多边形的费马点。所谓费马点,就是多边形中一个点P,该点到其他点的距离之和最短。四边形以上的多边形没有公式求费马点,因此可以使用随机化变步长贪心法。
详见:http://hi.baidu.com/novosbirsk/blog/item/75983f138499f825dd54019b.html
七。解析几何
这种题目本人不擅长,所以做得不多,模板很重要。当然,熟练运用叉积、点积的性质还是很有用的。
POJ 1375 Intervals
http://acm.pku.edu.cn/JudgeOnline/problem?id=1375
知识点:过圆外一点求与圆的切线
POJ 1329 Circle Through Three Points
http://acm.pku.edu.cn/JudgeOnline/problem?id=1329
求三角形外接圆
POJ 2354 Titanic
http://acm.pku.edu.cn/JudgeOnline/problem?id=2354
求球面上两个点的距离,而且给的是地理经纬坐标。
POJ 1106 Transmitters
http://acm.pku.edu.cn/JudgeOnline/problem?id=1106
角度排序,知道斜率求角度,使用atan函数。
POJ 1673 EXOCENTER OF A TRIANGLE
http://acm.pku.edu.cn/JudgeOnline/problem?id=1673
可以转化为三角形的垂心问题。
八。旋转卡壳
POJ 2187 Beauty Contest
http://acm.pku.edu.cn/JudgeOnline/problem?id=2187
凸包求最远点对。可以暴力枚举,也可以使用旋转卡壳。
POJ 3608 Bridge Across Islands(难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3608
两个凸包的最近距离。本人的卡壳始终WA。郁闷。
九。其他问题
POJ 1981 Circle and Points
http://acm.pku.edu.cn/JudgeOnline/problem?id=1981
求单位圆最多能覆盖平面上多少个点
posted @
2009-06-29 13:00 古月残辉 阅读(822) |
评论 (0) |
编辑 收藏
这题是判断线段相交,我的做法是枚举,由于题目数据中除了宝藏所在的点Point tar是浮点数,其余坐标全为整数,因此我采用的方法是把最外层每条边上的坐标的x或y坐标记录下来并排序,比如记录x=0的所有的点的y坐标在up[]数组中,其中,up[0]初始化为0。排序后,对每个数组中元素,将tar与(0,up[i]+0.5)组成一条边,判断它与每条边的交点数目即可,最后结果取最小值。
由于边的数目较小,因此这样做也蛮快的~~
代码copy下模板的就好了,注意,没有三面墙在同一交点,也就是说不存在不规范相交的情况,模板可以适当的改动~~
posted @
2009-06-29 12:48 古月残辉 阅读(432) |
评论 (0) |
编辑 收藏
![](/skins/sea/images/title_post.gif)
2009年3月14日
今天万里无云,什么叫万里无云,这真的是一点云也看不到啊,连只苍蝇也看不到……
从上次万里无云说起吧,那天心情很好,令人身心俱霉的烂冬天气终于结束了,我吃过晚饭,去九龙湖畔吹吹风,看看夕阳,走去的,路还蛮远的,在湖边的小桥上,看着鸳鸯戏水(也可能是别的什么鸟),看着夕阳西沉,感觉很宁静,只是奇怪的是夕阳的确沉下去了,问题是沉的那么早?我几番看表,都是5点多,时间有时候过的就是慢……
就这样,我傻B的在那边吹风吹到8点多(还是看手机短信才发现表停了)……
后来也不想看书了,就去图书馆逛逛吧,我那天特别走运,一去就找到了我一直想找的书,我那天特别不走运,在准备去借书的时候把那本书当成另一本没用的书恭恭敬敬的放回了书架(回去我还以为我书弄丢了,直到发现那本没用的书)……
再后来的一天中午,说是要卫生检查,听说辅导员可能要来,就大家一起抱个佛脚,把宿舍从里到翻新了一下,结果来的是两个女生……心想太没价值了,大呼:“梅梅怎么不来啊!“梅梅这个时候出现了(梅梅是我们辅导员……关键是她比我妈还大)……
还是那天中午,和雨帮同学开党员群众座谈会,我们把群众意见收集来了后去教室写,安静点嘛,等我甩腿到了教室,突然发现我没有信纸……四处借,借不到……回宿舍……时光是怎样匆匆流走的?我心里有自已的看法了……
继续,写完报告就要交,谁交呢?我自已想去交,因为我正好找辅导员有事,但就这么去了?不是我风格……我找到雨,他在补眠,正好。“报告我写好啦,你去交吧?”“Eng en en……”,嘿嘿,“那我交?”“恩!”“有什么好处不?”他来劲了坐起来和我把几乎从大一的账拿出来一笔一笔的算,算到一半的时候我悄无声息的溜出去了……自讨没趣……
我4点去辅导员办公室,那时天一阵雨一阵阴,我心想,速度去,办完事速度回!就骑了个车子冲到系办,结果,辅导员给四班开班会去了!而且才去不久。怎么办?等?不是我风格!我正好可以去把图书馆那本书再借回来嘛!我想它应该还在我放的位置上吧,就再骑个车子去借书,反正要等辅导员,不急,慢慢来,晃到图书馆,慢悠悠借到书,真是顺利啊,出门,下起了雨……怎么办?手上有书,还有伞,还要扶车,我没这技术,算了,果断点,走!我急匆匆的走到系办,已经5点了,辅导员再拖也该结束了吧!我对了,的确结束了,而且早就结束了,她已经回家了……天啊,怎么这么背啊,我出门,雨停了……
怎么办?回图书馆拿车?那么远,算了吧,还是去吃饭吧,下次有空再去拿,路过教学楼,顺便把书和伞放下,带那么多东西不方便啊,再说可能下雨吗?……可能!我吃完饭,淋着雨回来了……
怎么说那天心情都不太好,自习到10点多,回宿舍开黑(三个人手机上网QQ升级,两人一家,还有一个当奸细),想发泄下,我和小宝是一家,配合的很好,室长在对家,和我们配合的也很好……可是打牌,不仅要看配合,更要看手气啊,那天我输的郁郁而睡……
第二天早上起来,发现手机没电了,就在留在宿舍充电。上完课回来,速度要用手机。开机,自动关闭
?
再开机,再自动关闭
!
把充电器插头弄弄,手机插上去,没反应
?
换个插座,还是没反应
!
Shit!充电器怎么这个时候坏?!嗨,算了,去教室了,在电脑上面充吧……
下午写写程序,晚上吃完晚饭看到老爸在线,心想他打牌那么厉害,跟他蹭点分吧,开黑!可是这个世界就是这样,永远都有拆黑的同志,我们一上来就被打了两个光头……看着我从有车一族一路跌回赤脚,我心寒了。“老爸,我有点困了,你自已玩吧……”
晚上回宿舍,一如既往的Dota开黑,一如既往的被拆……宿舍四口郁郁而睡……
今天早上一觉醒来,万里无云,为什么呢?因为我跟别人说今天肯定下雨。为什么我这么说呢?因为我们班本来组织今天去春游,前不久和小朱约好去春游就是因为连下了2个多星期的雨而不了了之,根据经验,我下了这样的论断,即我们肯定去不了。我对了,因为我们没去成;我错了,因为没去成的原因是钱没谈好……
嗨,天晴了,心情也好些了,好好努力吧!
posted @
2009-03-14 14:06 古月残辉 阅读(263) |
评论 (0) |
编辑 收藏