12 Feb 10 A small visual tool for the problems of Computational Geomery
I call it vertion 1.0:)
It create a ps file which can be opened by Gsview.
Here it is:
- class Draw {
- private:
- FILE * file;
- P base;
- double rate;
- void moveto(P a) {
- fprintf(file, "%f %f moveto\n", a.x, a.y);
- }
- void lineto(P a) {
- fprintf(file, "%f %f lineto\n", a.x, a.y);
- }
- void show(const char *s) {
- fprintf(file, "(%s) show\n", s);
- }
- P update(P a) {
- return (a + base) * rate;
- }
- void done() {
- fprintf(file, "stroke\nshowpage\n");
- fclose(file);
- }
- public:
- Draw (const char * filename, double minx, double maxx, double miny, double maxy) {
- //file name must be *.ps. The next four arguments form the boundary of the plane.
- base = P(-minx, -miny);
- rate = min(499 / (maxx – minx), 499 / (maxy – miny));
- file = fopen(filename, "w");
- fprintf(file, "/Times-Roman findfont\n");
- fprintf(file, "20 scalefont\n");
- fprintf(file, "setfont\n");
- fprintf(file, "newpath\n");
- }
- ~Draw() {
- done();
- }
- void draw_segment(P a, P b) { //draw a segment.
- moveto(update(a));
- lineto(update(b));
- }
- void draw_line(P a, P b) {//draw a line
- a = update(a);
- b = update(b);
- moveto(a + (b – a).trunc(1000));
- lineto(b + (a – b).trunc(1000));
- }
- void draw_arc(P mid, double r = -1, double deg1 = -180, double deg2 = 180) {
- //draw arc; mid is the center of the circle. r is the radius.
- //deg1, deg2 are the range of the angle. (counter-clockwise).
- //if you want to draw a point just call draw_arc(mid),
- // and if you want to draw a circle, call draw(mid, r).
- r = r == -1? 1: r * rate;
- mid = update(mid);
- moveto(mid + P(cos(deg1 * pi / 180), sin(deg1 * pi / 180)) * r);
- fprintf(file, "%f %f %f %f %f arc\n", mid.x, mid.y, r, deg1, deg2);
- }
- template <class T> void draw_polygon(T s, T t) {//draw a polygon, use it in a way like stl.
- moveto(update(*s));
- while (s != t–) {
- lineto(update(*t));
- }
- }
- void draw_word(P p, const char *s, double sita, double len = 15) {//draw a word.
- //len is the distance between point p and the center of the first letter of the word.
- //sita is the slope of vector (P, center of the first letter).
- sita = sita * pi / 180 – pi / 8;
- moveto(update(p) + P(18 * cos(sita), 18 * sin(sita)));
- show(s);
- }
- };
12 Feb 10 My vimrc for ACM/ICPC, Version: 1.0
在这里发布一下我平时写竞赛小程序用的vimrc。
一是方便我自己备份，二是给有需要的人。
http://gaoyunxiang.com/wp-content/uploads/2010/02/vimrc.zip
使用方法：用上面的连接下载下来，里面有两个文件，一个是vimrc另一个_run.exe。
替换掉vimrc之后，把_run.exe放到和gvim.exe的同一个目录下。 (more…)
Tags: vimrc
11 Feb 10 An efficient algorithm for straight line in convex polygon queries
Description
Given a single convex polygon and a sequence of straight lines, quickly determine whether the straight line intersect with the convex polygon for each query straight line.
Algorithm
I’ll show you an efficient algorithm which can run in O(n – log(n)). It can also report the two intersections after running binary search. (more…)
Tags: Computational Geometry
09 Feb 10 Two efficient algorithms about Point in convex polygon queries
This problem can be described like this: Given a single convex polygon and a sequence of query points, quickly determine whether a point is in the polygon or not.
I’ll show you two efficient algorithm which can both run in O (n – log(n)). In addition, the first algorithm can expand to star-shaped polygon and the second can expand to monotone polygon.
Star-shaped polygon: a polygon P is called star-shaped if and only if there exists a point z such that for each point p of P the segment zp lies entirely within P.
Monotone polygon: a polygon P is called monotone with respect to a straight line L, if every line orthogonal to L intersects P at most twice. We call straight line L as the normal line of the polygon P.
Convex polygon is star-shaped and is also monotone with respect to any straight line.
The first algorithm:
1. Choose an edge AB and its midpoint P.
2. Link P to every vertex on the polygon so we can get n vectors which are already sorted by those slopes.
3. For each point X of a query, check if it is on the right side of vector AB. If it does, then return X is outside of the polygon. If it’s on line AB, then check if it is on the segment AB. If it does, then return X is on the edge AB of the polygon.
4. Now, we are sure that X is on the left side of vector AB. The next step, we use new vector PX to run a binary search which is based on the vectors we got at step 2, then we can get an interval where vector PX belongs. There must be an edge of the polygon in that interval.
5. Check the relation between the edge and the vector PX. Finally, we can get the answer.
In step 4, function atan2 can be use to get the slope of each vector, and then we run binary search by those slopes. Actually, we can run binary search on any objects as long as we define the “less” between them. Slope of course can be used to define “less”, but to be better we can use cross product to define “less” to get a more graceful implement.
Extend to star-shaped polygon:
Similar algorithm is possible for star-shaped polygon where we need to calculate the kernel first. Point P can be found in the kernel and “less” can also be defined by slopes or product cross.
Tags: Computational Geometry
08 Feb 10 Windows 7中的病毒Trojan.PWS.Legmir.AD / W32.Ahlem.A@mm
自从装了Win7之后,电脑总是是不是的提醒我电脑里有病毒.
Remove the Trojan.PWS.Legmir.AD / W32.Ahlem.A@mm virus from your computer
This problem was caused by Trojan.PWS.Legmir.AD / W32.Ahlem.A@mm, a known computer virus.
To prevent this problem from occurring again, install and run an up-to-date antivirus program on your computer.
刚看到这个提示消息的时候特别奇怪,我用电脑的习惯一直很好,从来没有装过杀毒软件,Win7又是一个新系统,安全性也挺高的,怎么会有病毒呢? 想当年用Win98的时候我都是裸奔…怎么Win7会提示中了病毒呢…
思索半天无果…只好把这个消息无视了.
不过最近还是频繁提示这个消息,郁闷了我好久…
这几天突发灵感,实验良久终于找到了问题所在.
原来是因为我写的程序a.exe被系统当作这个病毒了…
估计经常写小程序的人会碰到这个问题…大家都无视之吧,这个是Win7的误判…
07 Feb 10 HDOJ Monthly Contest – 2010.02.06 Problem “Key vertex”
http://acm.hdu.edu.cn/showproblem.php?pid=3313
这个题目的意思给一个有向图，然后问有多少个key vertexes。一个点是key vertex的定义是，删掉这个点之后这个图的S-T就不连通了。
网络流的做法是比较显然的。在拆点然后跑网络流之后，所有的点割就都是key vertex。
题目里的点数比较多，有100000个之多，怎么求得高效的求得所有的点割是这个题目的另一个关键。
仔细观察残余网络的性质之后，可以得出一下算法：
- 在残余网络中bfs，直到走不动了，就找到了第一个割。
- 而后把这个割在残余网络中连通，并且继续bfs（进行第一步的操作）。
这个做法的精巧实现使可以做到线性的。
Tags: HDOJ Monthly, 图论, 网络流
07 Feb 10 POJ Monthly Contest – 2010.1.24 – Problem A "Cake"
http://poj.grids.cn/contest/1774/problem-A/
这个题目是我出的，题意写的有点晦涩-.-!
不过简单表述起来还是挺简单的。
就是在一个圆上进行切割，每一次切割都要跨过整个圆。然后需要检查切割线，检查切割线的方法就是碰触切割出来的每一个小块。
说白了就是小块为点，相邻的小块连边，然后问进行点涂色，使得每一个边的两个端点至少有一个是涂色过了的。
解法：
通过一系列比较麻烦的几何处理之后，所求出来的图是一个二分图。然后求得二分匹配就是答案。
关于这个图是二分图的证明也有比较形象的理解，就是这个图是明显没有奇环的，所以就是二分图咯。。。
Tags: Poj Monthly, 图论, 计算几何
07 Feb 10 HDOJ Monthly 2009.01 Problem "Light"
http://acm.hdu.edu.cn/showproblem.php?pid=3275
这个题目比较简单。。。
我刚开始写的解题报告里面说：
Greedy algorithm and Segment Tree will be worked at this problem.
We need change all “0” to “1”, so let’s put our attention on the first lantern of the given string. There is only one way to change states of first lantern which is installing a switch to control the first k lanterns.
Algorithm:
- If the first lantern is off then install a switch to change the states of first k lanterns.
- Let the second lantern be the first one and repeat Step 1 until there are less than k lanterns.
- If all of the remaining lanterns are on then output the answer else output “-1”.
Native solution will get TLE as it’s running in O(n * k).
A new accelerated date structure should be used to storage all the states of lanterns. This date structure should support two operators.
- Find the states of one lantern.
- Change all states of an interval.
Segment Tree will be worked.
这里说的线段树其实就是区间覆盖那种，统计一个点的奇偶值就查看这个点被覆盖的总数就好了。
因为这里的区间的大小总是K，所以其实用不着线段树，线性扫描就好了。。。
Tags: HDOJ Monthly, 线段树, 贪心
07 Feb 10 dancing links 的简单介绍及应用
很早以前写的一个文章的初稿。可惜的是底稿找不到了。。。
很多内容都没有修正和添加，不过大体内容差不多，有兴趣的将就着看看吧。
地址如下：
http://gaoyunxiang.com/wp-content/uploads/2010/02/Dancing_Links.pdf
Tags: dancing links
1,106 | Unique Visitors |
