The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

#

discovery(探索发现)下载地址

     摘要: 美国探索节目  阅读全文

posted @ 2009-08-26 11:18 abilitytao 阅读(1406) | 评论 (0)编辑 收藏

差分约束系统(System Of Difference Constraints)

(本文假设读者已经有以下知识:最短路径的基本性质、Bellman-Ford算法。)
    比如有这样一组不等式:
   
X1 - X2 <= 0
X1 - X5 <= -1
X2 - X5 <= 1
X3 - X1 <= 5
X4 - X1 <= 4
X4 - X3 <= -1
X5 - X3 <= -3
X5 - X4 <= -3
不等式组(1)

    全都是两个未知数的差小于等于某个常数(大于等于也可以,因为左右乘以-1就可以化成小于等于)。这样的不等式组就称作差分约束系统。
    这个不等式组要么无解,要么就有无数组解。因为如果有一组解{X1, X2, ..., Xn}的话,那么对于任何一个常数k,{X1 + k, X2 + k, ..., Xn + k}肯定也是一组解,因为任何两个数同时加一个数之后,它们的差是不变的,那么这个差分约束系统中的所有不等式都不会被破坏。
   
    差分约束系统的解法利用到了单源最短路径问题中的三角形不等式。即对于任何一条边u -> v,都有:

d(v) <= d(u) + w(u, v)

    其中d(u)和d(v)是从源点分别到点u和点v的最短路径的权值,w(u, v)是边u -> v的权值。
    显然以上不等式就是d(v) - d(u) <= w(u, v)。这个形式正好和差分约束系统中的不等式形式相同。于是我们就可以把一个差分约束系统转化成一张图,每个未知数Xi对应图中的一个顶点Vi,把所有不等式都化成图中的一条边。对于不等式Xi - Xj <= c,把它化成三角形不等式:Xi <= Xj + c,就可以化成边Vj -> Vi,权值为c。最后,我们在这张图上求一次单源最短路径,这些三角形不等式就会全部都满足了,因为它是最短路径问题的基本性质嘛。
    话说回来,所谓单源最短路径,当然要有一个源点,然后再求这个源点到其他所有点的最短路径。那么源点在哪呢?我们不妨自已造一个。以上面的不等式组为例,我们就再新加一个未知数X0。然后对原来的每个未知数都对X0随便加一个不等式(这个不等式当然也要和其它不等式形式相同,即两个未知数的差小于等于某个常数)。我们索性就全都写成Xn - X0 <= 0,于是这个差分约束系统中就多出了下列不等式:
   
X1 - X0 <= 0
X2 - X0 <= 0
X3 - X0 <= 0
X4 - X0 <= 0
X5 - X0 <= 0

不等式组(2)

    对于这5个不等式,也在图中建出相应的边。最后形成的图如下:


图1

    图中的每一条边都代表差分约束系统中的一个不等式。现在以V0为源点,求单源最短路径。最终得到的V0到Vn的最短路径长度就是Xn的一个解啦。从图1中可以看到,这组解是{-5, -3, 0, -1, -4}。当然把每个数都加上10也是一组解:{5, 7, 10, 9, 6}。但是这组解只满足不等式组(1),也就是原先的差分约束系统;而不满足不等式组(2),也就是我们后来加上去的那些不等式。当然这是无关紧要的,因为X0本来就是个局外人,是我们后来加上去的,满不满足与X0有关的不等式我们并不在乎。
    也有可能出现无解的情况,也就是从源点到某一个顶点不存在最短路径。也说是图中存在负权的圈。这一点我就不展开了,请自已参看最短路径问题的一些基本定理。

    其实,对于图1来说,它代表的一组解其实是{0, -5, -3, 0, -1, -4},也就是说X0的值也在这组解当中。但是X0的值是无可争议的,既然是以它作为源点求的最短路径,那么源点到它的最短路径长度当然是0了。因此,实际上我们解的这个差分约束系统无形中又存在一个条件:

X0 = 0

    也就是说在不等式组(1)、(2)组成的差分约束系统的前提下,再把其中的一个未知数的值定死。这样的情况在实际问题中是很常见的。比如一个问题表面上给出了一些不等式,但还隐藏着一些不等式,比如所有未知数都大于等于0或者都不能超过某个上限之类的。比如上面的不等式组(2)就规定了所有未知数都小于等于0。
   
    对于这种有一个未知数定死的差分约束系统,还有一个有趣的性质,那就是通过最短路径算法求出来的一组解当中,所有未知数都达到最大值。下面我来粗略地证明一下,这个证明过程要结合Bellman-Ford算法的过程来说明。
    假设X0是定死的;X1到Xn在满足所有约束的情况下可以取到的最大值分别为M1、M2、……、Mn(当然我们不知道它们的值是多少);解出的源点到每个点的最短路径长度为D1、D2、……、Dn。
    基本的Bellman-Ford算法是一开始初始化D1到Dn都是无穷大。然后检查所有的边对应的三角形不等式,一但发现有不满足三角形不等式的情况,则更新对应的D值。最后求出来的D1到Dn就是源点到每个点的最短路径长度。
    如果我们一开始初始化D1、D2、……、Dn的值分别为M1、M2、……、Mn,则由于它们全都满足三角形不等式(我们刚才已经假设M1到Mn是一组合法的解),则Bellman-Ford算法不会再更新任合D值,则最后得出的解就是M1、M2、……、Mn。
    好了,现在知道了,初始值无穷大时,算出来的是D1、D2、……、Dn;初始值比较小的时候算出来的则是M1、M2、……、Mn。大家用的是同样的算法,同样的计算过程,总不可能初始值大的算出来的结果反而小吧。所以D1、D2、……、Dn就是M1、M2、……、Mn。
   
    那么如果在一个未知数定死的情况下,要求其它所有未知数的最小值怎么办?只要反过来求最长路径就可以了。最长路径中的三角不等式与最短路径中相反:

d(v) >= d(u) + w(u, v)
也就是 d(v) - d(u) >= w(u, v)


    所以建图的时候要先把所有不等式化成大于等于号的。其它各种过程,包括证明为什么解出的是最小值的证法,都完全类似。
    
    用到差分约束系统的题目有ZJU 2770,祝好运。

转自:http://imlazy.ycool.com/post.1702305.html

posted @ 2009-08-21 23:34 abilitytao 阅读(2264) | 评论 (6)编辑 收藏

POJ 3322 Bloxorz I(BFS, 改编自同名游戏,很不错的一题)

     摘要: Bloxorz I Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 2624 Acce...  阅读全文

posted @ 2009-08-16 22:25 abilitytao 阅读(1725) | 评论 (4)编辑 收藏

POJ 1631 Bridging signals——最长上升子序列 DP(nlogn)

题目说了很多,其实就是一个最长上升子序列的问题,传统的n^2算法在这里会超时,所以改用二分的算法,1000MS的时限用掉110MS,差强人意,但不知还有没有更快的算法,希望各位大牛能指点一二。
代码如下:(阅读前建议先阅读我转的上一篇关于算法介绍的文章)
#include<iostream>
#include
<cstdio>
using namespace std;


const int N =  40000;

int a[N], C[N], f[N]; // f[i]用于记录a[0i]的最大长度

int bsearch(const int *C, int size, const int &a) 

{
    
    
int l=0, r=size-1;
    
    
while( l <= r ) 
        
    
{
        
        
int mid = (l+r)/2;
        
        
if( a > C[mid-1&& a <= C[mid] ) return mid; // >&&<= 换为: >= && <
        
        
else if( a < C[mid] ) r = mid-1;
        
        
else l = mid+1;
        
    }

    
}


int LIS(const int *a, const int &n){
    
    
int i, j, size = 1;
    
    C[
0= a[0]; f[0= 1;
    
    
for( i=1; i < n; ++i ){
        
        
if( a[i] <= C[0] ) j = 0;                 // <= 换为: <
        
        
else if( a[i] >C[size-1] ) j = size++;   // > 换为: >= 
        
        
else j = bsearch(C, size, a[i]);
        
        C[j] 
= a[i]; f[i] = j+1;
        
    }

    
    
return size;
    
}




int main()
{
    
int testcase;
    
int n;
    scanf(
"%d",&testcase);
    
int i,j;
    
for(i=1;i<=testcase;i++)
    
{
        scanf(
"%d",&n);
        
for(j=0;j<n;j++)
            scanf(
"%d",&a[j]);
        printf(
"%d\n",LIS(a,n));
    }

    
return 0;
}

posted @ 2009-08-12 19:14 abilitytao 阅读(1837) | 评论 (1)编辑 收藏

最长不降子序列的nlogn算法 (转)

所谓“最长不降子序列问题”,就是在一个给定的序列中寻找一个子序列{ai}满足:

                       a1<=a2<=...<an

这个问题在一般教材上,往往会作为动态规划的引例。

即使用如下的状态转移方程进行计算:

                   F[i]=max{F[j]}+1     aj<=ai

但是它的复杂度是O(n^2)的,对于稍大的规模便无法承受。

那么有没有改进的方法呢?答案是肯定的。

----------------------------------------------------------------分割线------------------------------------------------------------------------------------------

我们维护一个数组C[i],这里C[i]表示F值为i的最小数。

不难发现   C[1]<=C[2]<=...<=C[n]

因此我们可以利用C[]通过二分查找确定F[j]的值。

----------------------------------------------------------------分割线------------------------------------------------------------------------------------------

实现如下:

const int N = 1001;

int a[N], C[N], f[N]; // f[i]用于记录a[0...i]的最大长度

int bsearch(const int *C, int size, const int &a)

{

    int l=0, r=size-1;

    while( l <= r )

    {

        int mid = (l+r)/2;

        if( a > C[mid-1] && a <= C[mid] ) return mid; // >&&<= 换为: >= && <

        else if( a < C[mid] ) r = mid-1;

        else l = mid+1;

    }

}

int LIS(const int *a, const int &n){

     int i, j, size = 1;

     C[0] = a[0]; f[0] = 1;

     for( i=1; i < n; ++i ){

          if( a[i] <= C[0] ) j = 0;                 // <= 换为: <

         else if( a[i] >C[size-1] ) j = size++;   // > 换为: >=

         else j = bsearch(C, size, a[i]);

         C[j] = a[i]; f[i] = j+1;

     }

     return size;

}

------------------------------------------------------------------分割线------------------------------------------------------------------------------------------

至此,我们了解了O(nlogn)的算法,它主要是利用了二分查找的方法对朴素的动态规划进行加速、优化,从而达到理想的效率。



转自:http://fqq11679.blog.hexun.com/21632261_d.html

posted @ 2009-08-12 18:27 abilitytao 阅读(385) | 评论 (0)编辑 收藏

POJ 计算几何入门题目推荐(转)

计算几何题的特点与做题要领:
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的关系)

四。半平面交

半平面交的主要应用是判断多边形是否存在核,还可以解决一些与线性方程组可行区域相关的问题(就是高中时的那些)。

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-08-07 01:15 abilitytao 阅读(1742) | 评论 (0)编辑 收藏

POJ 1066——Treasure Hunt解题报告

我刚开始被这道题目的名字吸引了,因为它和宝藏有关,呵呵^_^不过把题目读完以后才发现这道题是个无聊的计算几何题 ,说实话有点失望。。。

题目的大意是这样的:寻宝者在一个被分割成很多房间的正方形迷宫里寻宝,这个迷宫是100*100的正方形而且四个顶点坐标一定。寻宝者具有把墙凿穿通过的能力,若寻宝者可以从正方形的任意一个边界进入,问到达藏宝地点最少要穿过几道墙?

这个题的解法是:枚举每一个入口。然后在所有的情况中取穿墙数最少的输出即可。
考察每一个入口的时候,枚举每条边,如果起点和终点在这条直线的两侧,那么寻宝者一定要穿过一道墙。于是此题转化成了判断2点是否在一条直线的异侧的问题。模板解决~

由于自己写的有点冗长,于是参考了下网上的代码,发现将所有边界上的点按照角度排序的确是个很巧妙的方法,学习了^_^

//coded by abilitytao
//Time:2009年8月5日17:50:19

#include
<iostream>
#include
<cmath>
#include
<algorithm>
using namespace std;
double const EPS = 1e-8;
const int INF = 0xf777777;
#define zero(x) (((x)>0?(x):-(x))<eps) 



struct Point
{
    
double x,y;
    Point()
{}
       Point(
double a, double b):x(a), y(b){}
       
bool operator<(Point a){return atan2(y - 50, x - 50< atan2(a.y - 50, a.x - 50); }
}


struct Line// 定义一条线段,用起点和终点来表示 
{               
    Point a, b; 
    Line() 
{} 
    Line(Point p10, Point p20): a(p10), b(p20) 
{} //Line a(p1,p2);
}



Point mypoint[
64], s, t;
Line myline[
30];
int n, countnum, minnum;

double xmult(Point p1, Point p2 , Point p0)
{
    
return (p1.x - p0.x)*(p2.y - p0.y)-(p2.x - p0.x)*(p1.y - p0.y);
}

int same_side(Point p1,Point p2,Line l)

    
return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)>EPS; 
}


int main()
{
    
int i, j, ans;
    minnum 
= INF; countnum = 0;
    mypoint[countnum
++= Point(00);
    mypoint[countnum
++= Point(1000);
    mypoint[countnum
++= Point(0100);
    mypoint[countnum
++= Point(100100);
    
    cin 
>> n;
    
for(i = 0; i < n; i++)
    
{
        scanf(
"%lf%lf%lf%lf",&myline[i].a.x ,&myline[i].a.y ,&myline[i].b.x ,&myline[i].b.y);
        mypoint[countnum
++= myline[i].a;
        mypoint[countnum
++= myline[i].b;
    }

    scanf(
"%lf%lf",&s.x,&s.y);
    
       sort(mypoint, mypoint
+countnum);
       
       
for(i=0;i<countnum;i++ )
       
{
           ans 
= 0;
           t 
= Point( (mypoint[i].x + mypoint[(i+1)%countnum].x)/2, (mypoint[i].y + mypoint[(i+1)%countnum].y)/2 );
           
for(j = 0; j < n; j++)          
               
if(!same_side(s, t, myline[j]))
                   ans
++;
            
if(ans <minnum) minnum = ans;
       }

       
       printf(
"Number of doors = %d\n", minnum+1);
       
return 0;
}

posted @ 2009-08-05 23:58 abilitytao 阅读(1522) | 评论 (0)编辑 收藏

2009年ACM-ICPC亚洲区预选赛共设十五个赛区如下(按现场赛日期排序):

1、Harbin 哈尔滨赛区(哈尔滨工业大学)
网络选拔赛日期:2009年9月13日 14:00-17:00
现场赛日期:2009年9月26日~27日
http://acm.hit.edu.cn/

2、Dhaka 达卡赛区(孟加拉国 Northsouth University)
现场赛日期:2009年10月3日
http://www.northsouth.edu/acm/

3、Gwalior-Kanpur 瓜廖尔-坎普尔赛区(印度 IIITM Gwalior and Indian Institute of Technology, India)
现场赛日期:2009年10月3日~4日
http://www.cse.iitk.ac.in/users/acm/

4、Hefei 合肥赛区(中国科学技术大学)
网络选拔赛日期:2009年9月6日 14:00-17:00
现场赛日期:2009年10月10日~11日
http://acm.ustc.edu.cn/

5、Ningbo 宁波赛区(浙江大学宁波理工学院)
网络选拔赛日期:2009年9月12日
现场赛日期:2009年10月17日~18日
http://acmasia09.nit.net.cn/

6、Jakarta 雅加达赛区(印尼 Binus University)
现场赛日期:2009年10月21日
http://icpc.ewubd.edu/

7、Manila 马尼拉赛区(菲律宾 Ateneo de Manila University)
现场赛日期:2009年10月22日~23日
http://www.math.admu.edu.ph/acm/

8、Shanghai 上海赛区(东华大学)
网络选拔赛日期:2009年9月20日(12:00-17:00)
现场赛日期:2009年10月24日~25日
http://acm.dhu.edu.cn

9、Hsinchu 新竹赛区(交通大学)
报名截止日期:2009年8月19日
现场赛日期:2009年10月30日~31日
http://icpc2009.nctu.edu.tw/

10、Wuhan 武汉赛区(武汉大学)
网络选拔赛日期:2009年10月3
现场赛日期:2009年10月31日~11月1日
http://acm.whu.edu.cn/

11、Amritapuri 阿姆里塔普里赛区(印度 Amrita Vishwa Vidyapeetham, Amritapuri Campus)
现场赛日期:2009年11月1日
http://icpc.amrita.ac.in/

12、Phuket 普吉岛赛区(泰国 Prince of Songkla University, Phuket Campus)
报名截止日期:2009年9月30日
现场赛日期:2009年11月3日~4日
http://www.acmicpc-thailand.org/

13、Seoul 首尔赛区(韩国 Korea Advanced Institute of Science and Technology)
报名截止日期:2009年9月11日
现场赛日期:2009年11月5日~6日
http://acm.kaist.ac.kr/

14、Tehran 德黑兰赛区(伊朗 Sharif University of Technology)
现场赛日期:2009年11月6日
http://sharif.edu/~acmicpc

15、Tokyo 东京赛区(日本早稻田大学)
现场赛日期:2009年11月7日~8日
http://www.waseda.jp/assoc-icpc2009/en/index.html

参赛报名网址

http://cm.baylor.edu/welcome.icpc

亚洲高校可组队参加全部十五个赛区的预选赛,但每位参赛选手最多只能注册参加两个赛区的预选赛。

posted @ 2009-08-04 17:08 abilitytao 阅读(1701) | 评论 (0)编辑 收藏

计算几何模板整理

#include<iostream>
#include
<cmath>
#include
<algorithm>
using namespace std;

struct Point // 定义一个点
{              
    
double x, y;  
    Point() 
{} 
    Point(
double x0, double y0): x(x0), y(y0) {} //Point a(1.0,2.0);
}


struct Line// 定义一条线段,用起点和终点来表示 
{               
    Point p1, p2; 
    Line() 
{} 
    Line(Point p10, Point p20): p1(p10), p2(p20) 
{} //Line a(p1,p2);
}


//定义叉积:
//1.如果返回值为正数,表明sp在op->ep(op指向ep)这条射线的顺时针方向;
//2.如果返回值为负数,表明sp在op->ep(op指向ep)这条射线的逆时针方向;
//3.如果返回值为0,表明三点共线
double multiply(Point sp,Point ep,Point op)
{
    
return((sp.x-op.x)*(ep.y-op.y) - (ep.x-op.x)*(sp.y-op.y));
}

posted @ 2009-08-04 16:35 abilitytao 阅读(175) | 评论 (0)编辑 收藏

POJ 2318 toys 叉积的简单运用

题目意思很简单,把一个盒子分成很多部分,往盒子里扔小球,小球的落点当然要告诉你拉,让你统计每个盒子里最后拥有的小球数。
我的做法是叉积+二分。
#include<iostream>
#include
<cmath>
#include
<algorithm>
using namespace std;

struct Point 
{              // 二维点或矢量 
    double x, y;  
    Point() 
{} 
    Point(
double x0, double y0): x(x0), y(y0) {} 
}


struct Line
 
{               // 二维的直线或线段 
    Point p1, p2; 
    Line() 
{} 
    Line(Point p10, Point p20): p1(p10), p2(p20) 
{} 
}



double multiply(Point sp,Point ep,Point op)
{
    
return((sp.x-op.x)*(ep.y-op.y) - (ep.x-op.x)*(sp.y-op.y));
}




Line myline[
5100];
int record[5100];


int main()
{

    
int n,m,i;
    Point left;
    Point right;
    
while(scanf("%d",&n))
    
{

        
if(n==0)
            
break;
        memset(record,
0,sizeof(record));
        scanf(
"%d%lf%lf%lf%lf",&m,&left.x,&left.y,&right.x,&right.y);
        myline[
0].p1.x=left.x;
        myline[
0].p1.y=right.y;
        myline[
0].p2.x=left.x;
        myline[
0].p2.y=left.y;
        
for(i=1;i<=n;i++)
        
{
            scanf(
"%lf%lf",&myline[i].p2.x,&myline[i].p1.x);
            myline[i].p1.y
=right.y;
            myline[i].p2.y
=left.y;

        }

        myline[n
+1].p1.x=right.x;
        myline[n
+1].p1.y=right.y;
        myline[n
+1].p2.x=right.x;
        myline[n
+1].p2.y=left.y;
        
        Point toy;
        
for(i=1;i<=m;i++)
        
{
            scanf(
"%lf%lf",&toy.x,&toy.y);
            
int front=0;
            
int rear=n+1;
            
while(front<=rear)
            
{

                
int mid=(front+rear)>>1;
                
if(multiply(toy,myline[front].p2,myline[front].p1)>0&&multiply(toy,myline[mid].p2,myline[mid].p1)<0)
                
{

                    
if(mid==front+1)
                    
{
                        record[front]
++;
                        
break;
                    }

                    rear
=mid;
                    
continue;
                }

                
else
                
{

                    
if(mid+1==rear)
                    
{
                        record[mid]
++;
                        
break;
                    }

                    front
=mid;
                    
continue;
                }


            }

        }


        
for(i=0;i<=n;i++)
        
{
            printf(
"%d: %d\n",i,record[i]);
        }

        printf(
"\n");
    }

    
return 0;
}


恭喜此题成为我收集计算几何模板的第一题 呵呵~

posted @ 2009-08-04 16:26 abilitytao 阅读(896) | 评论 (1)编辑 收藏

仅列出标题
共42页: First 26 27 28 29 30 31 32 33 34 Last