2012年6月29日 星期五

uva 10301 - Rings and Glue

10301 - Rings and Glue


Problem B
Rings and Glue
Input: standard input
Output: standard output
Time Limit: 1 second
Memory Limit: 32 MB

Little John is in big trouble. Playing with his different-sized (and colored!) rings and glue seemed such a good idea. However, the rings now lay on the floor, glued together with some-thing that will definitely not come off with water. Surprisingly enough, it seems like no rings are actually glued to the floor, only to other rings. How about that!

You must help Little John to pick the rings off the floor before his mom comes home from work. Since the glue is dry by now, it seems like an easy enough task. This is not the case. Little John is an irrational kid of numbers, and so he has decided to pick up the largest component (most rings) of glued-together rings first. It is the number of rings in this largest component you are asked to find. Two rings are glued together if and only if they overlap at some point but no rings will ever overlap in only a single point. All rings are of the doughnut kind (with a hole in them). They can however, according to Little John, be considered “infinitely thin”.

Input
Input consists of a number (>0) of problems. Each problem starts with the number of rings, n, where 0 £ n < 100. After that, n rows follow, each containing a ring’s physical attributes. That is, 3 floating point numbers, with an arbitrary number of spaces between them, describing the x coordinate and y coordinate for its center and its radius. All floating point numbers fit into the standard floating point type of your favorite programming language (e.g., float for C/C++). Input ends with a single row with the integer -1.

Output
Output consists of as many grammatically correct answers as there were problems, each answer, on a separate line, being ‘The largest component contains X ring(s).’ where X is the number of rings in the largest component.

Sample Input
4
0.0 0.0 1.0
-1.5 -1.5 0.5
1.5 1.5 0.5
-2.0 2.0 3.5
3
3.0 2.0 2.0
0.0 -0.5 1.0
0.0 0.0 2.0
5
-2.0 0.0 1.0
1.0 -1.0 1.0
0.0 1.0 0.5
2.0 0.0 1.0
-1.0 1.0 1.0
-1

Sample Output
The largest component contains 4 rings.
The largest component contains 2 rings.
The largest component contains 3 rings.
(Joint Effort Contest, Problem Source: Swedish National Programming Contest, arranged by department of Computer Science at Lund Institute of Technology.)
geometry

張貼者： 於 沒有留言:
標籤：

線段樹(Segment Tree)

source: http://www.cnblogs.com/tanky_woo/archive/2010/09/25/1834523.html

線段樹(Segment Tree)

实际上还是称为区间树更好理解一些。
树：是一棵树，而且是一棵二叉树。
线段：树上的每个节点对应于一个线段(还是叫“区间”更容易理解，区间的起点和终点通常为整数)
同一层的节点所代表的区间，相互不会重叠。
叶子节点的区间是单位长度，不能再分了。

线段树是一棵二叉树，树中的每一个结点表示了一个区间[a,b]。a,b通常是整数。每一个叶子节点表示了一个单位区间。对于每一个非叶结点所表示的结点[a,b]，其左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2,b](除法去尾取整）。
线段树的基本用途：
线段树适用于和区间统计有关的问题。比如某些数据可以按区间进行划分，按区间动态进行修改，而且还需要按区间多次进行查询，那么使用线段树可以达到较快查询速度。
线段树的构建
   createSeg   //以节点v为根建树、v对应区间为[l,r]
{
    对节点v初始化
     if (l!=r)
    {
        以v的左孩子为根建树、区间为[l,(l+r)/2]
        以v的右孩子为根建树、区间为[(l+r)/2+1,r]
    }
}
(浏览器似乎不太好用了，上面的代码点“插入代码”不管用，就直接贴出来了)

个人感觉线段树比较灵活，要多做一些题目才能对线段树有一个大概的掌握。
网上看见了一些线段树的资料，这里也贴出来。
线段树(区间树)Segment Tree
張貼者： 於 沒有留言:
標籤： ,

Network Flow

source: http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=f3cec71910d4a0106624e839f2891b17198ef58be


網路流 Network Flow

(Network Flow)是近年來在圖論中相當熱門的問題，在
1955 年 ，T.E. Harris 在研究鐵路最大通量時，首先提出在一個給定
的網路上尋求兩點間最大運輸量的問題。1956 年，L.R. Ford 和 D.R.
Fulkerson 給出解決這類問題的演算法，從而建立了網路流理論。
最大流問題的研究密切了圖論和運籌學，特別是與線性規劃的聯繫，開闢了圖論應用的新途徑。
關於網路流的定義 Definitions of Network Flow
1. 網路(Network)：圖 G = ( V, A )為一有向圖，稱為網路
2. 源點與匯點(Source and Sink)：令一點 S 為源點、一點 T 為匯點，其餘點則為中間點
3. 容量(Capacity)：每條弧上定義一個非負數 C(u, v)
4. 流量(Flow)：每條弧上定義一個 F(u, v) ，所有 。
5. 剩餘容量(Residual Capacity)：每條弧上定義一個 Cf(u, v) = C(u, v) – F(u, v) 為該弧的剩餘
容量，而剩餘容量的集合則稱為剩餘網路(Residual Network)
6. 網路的流量(Flow of Network)：由源點發出，匯點匯集的總流量 ，，， ，若其為該網路能產生的
量，則稱其為 量量量 (Maximum Flow)。 ...
張貼者： 於 沒有留言:
標籤：

Splay Tree


Demo: http://www.link.cs.cmu.edu/cgi-bin/splay/splay-cgi.pl

source:  http://www.fcicq.net/wp/?p=107

Splay Tree – 伸展树


假设想要对一个二叉查找树执行一系列的查找操作。为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计 一个简单方法，在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。splay tree应运而生。splay tree是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。

重构方法

1、单旋：在查找完位于节点x中的条目i之后，旋转链接x和其父节点的边。（除非x就是树根）
2、搬移至树根：在查找完位于节点x中的条目i之后，旋转链接x和其父节点的边，然后重复这个操作直至x成为树根。
splay tree的重构方法和搬移至树根的方法相似，它也会沿着查找路径做自底向上的旋转，将被查找条目移至树根。但不同的是，它的旋转是成对进行的，顺序取决于查找路径的结构。为了在节点x处对树进行splay操作，我们需要重复下面的步骤，直至x成为树根为止：
1、第一种情况：如果x的父节点p(x)是树根，则旋转连接x和p(x)的边。（这种情况是最后一步）
2、第二种情况：如果p(x)不是树根，而且x和p(x)本身都是左孩子或者都是右孩子，则先旋转连接p(x)和x的祖父节点g(x)的边，然后再旋转连接x和p(x)的边。
3、第三种情况：如果p(x)不是树根，而且x是左孩子，p(x)是右孩子，或者相反，则先旋转连接x和p(x)的边，再旋转连接x和新的p(x)的边。
在节点x处进行splay操作的时间是和查找x所需的时间成比例的。splay操作不单是把x搬移到了树根，而且还把查找路径上的每个节点的深度都大致减掉了一半。

splay tree支持的操作

1、access(i,t):如果i在树t中，则返回指向它的指针，否则返回空指针。为了实现access(i,t)，可以从树t的根部向下查找 i。如果查找操作遇到了一个含有i的节点x，就在x处进行splay操作，并返回指向x的指针，访问结束。如果遇到了空指针，表示i不在树中，此时就在最 后一个非空节点处进行splay操作，然后返回空指针。如果树是空的，将忽略掉splay操作。
2、insert(i,t):将条目i插入树t中（假设其尚不存在）。为了实现insert(i,t)，首先执行split(i,t)，然后把t换成一个由新的包含有i的根节点组成的树，这个根节点的左右子树分别是split返回的树t1和t2。
3、delete(i,t):从树t中删除条目i（假设其已经存在）。为了实现delete(i,t)，首先执行access(i,t)，然后把t换成其左子树和右子树join之后的新树。
4、join(t1,t2):将树t1和t2合并成一棵树，其中包含之前两棵树的所有条目，并返回合并之后的树。这个操作假设t1中的所有条目都小于t2 中的条目，操作完成之后会销毁t1和t2。为了实现join(t1,t2)，首先访问t1中最大的条目i。访问结束之后，t1的根节点中包含的就是i，它 的右孩子显然为空。于是把t2作为这个根节点的右子树并返回完成之后的新树即可实现join操作。
5、split(i,t):构建并返回两棵树t1和t2，其中t1包含t中所有小于等于i的条目，t2包含t中所有大于i的条目。操作完成之后销毁t。为 了实现split(i,t)，首先执行access(i,t)，然后根据新根节点中的值是大于还是小于等于i来切断这个根节点的左链接或右链接，并返回形 成的两棵树。

Splay Tree的优势所在

由于Splay Tree仅仅是不断调整，并没有引入额外的标记，因而树结构与标准BST没有任何不同，从空间角度来看，它比Treap、Red-Black Tree、AVL要高效得多。因为结构不变，因此只要是通过左旋和右旋进行的操作对Splay Tree性质都没有丝毫影响，因而它也提供了BST中最丰富的功能，包括快速的拆分和合并（这里指的是将原树拆分成两棵子树，其中一棵子树所有节点都比另 一子树小，以及它的逆过程），并且实现极为便捷。这一点是其它结构较难实现的。其时间效率也相当稳定，和Treap基本相当。
張貼者： 於 沒有留言:
標籤： ,

[uva] 10451 - Ancient Village Sports


Problem H
Ancient Village Sports
Input: standard input
Output: standard output
Time Limit: 30 seconds

In an ancient village there lived a number of people who liked different sorts of sports very much. But there was no built-in sports-ground. So they started looking for places. Ultimately what they found were the surfaces of the rocks with a shape of a regular polygon. Since the spectators are the part and parcel of the game, they must have some place over the ground. Again, officials of the teams must also have some space. They chose the in circle or striped portion of the regular polygon as the playing ground. They decided to leave the dotted portion as indicated in the figure for spectators and the criss-crossed portion for the officials. The diagonally striped portion is used for playing the game. You are going to help them to find the area of these portions.  


A polygon is regular if all its sides are equal and all its angles are equal. Either of the conditions implies the other in the case of a triangle, but not in general. A rhombus has equal sides but not necessarily equal angles, and a rectangle has equal angles but not necessarily equal sides. So rhombus and rectangle are not regular polygons.


You are given the area (A) of an n-sided regular polygon. You are to determine the total area for the spectators and the total area for the officials. Assume that π= 2*cos-1(0)

Input

In each line of the input file there is an integer n (0 and a floating-point number A (0<=A<=30000). A line with the value of n is less than three, terminates the input.

Output
For each line of input (except the last one) you should produce one line of output. This line contains the serial no of output as shown in the sample output followed by two floating-point numbers separated by a single space. The first one gives the area for the spectators and the second one gives that of the officials. There is also a single space between the colon and first floating point number. The floating-point numbers has five digits after the decimal point.

 

Sample Input

3 0.43301
6 2.59808
9 6.18182

0 2.33333

                          

Sample Output

Case 1: 0.61418 0.17121
Case 2: 0.54352 0.24188
Case 3: 0.53226 0.25314
Problem-setter: Tanbir Ahmed, CSE Department, Southeast University


geometry 
張貼者： 於 沒有留言:
標籤： ,
訂閱： 文章 (Atom)