# CG2017 PA1-1 Convex Hull (凸包)

### Description (描述)

After learning Chapter 1, you must have mastered the convex hull very well. Yes, convex hull is at the kernel of computational geometry and serves as a fundamental geometric structure. That’s why you are asked to implement such an algorithm as your first programming assignments.

Specifically, given a set of points in the plane, please construct the convex hull and output an encoded description of all the extreme points.

### Input (输入)

The first line is an integer n > 0, i.e., the total number of input points.

The k-th of the following n lines gives the k-th point:

pk = (xk, yk), k = 1, 2, …, n

Both xk and yk here are integers and they are delimited by a space.

pk = (xk, yk), k = 1, 2, …, n

### Output (输出)

Let { s1, s2, …, sh } be the indices of all the extreme points, h ≤ n. Output the following integer as your solution:

( s1 * s2 * s3 * … * sh * h ) mod (n + 1)

( s1 * s2 * s3 * … * sh * h ) mod (n + 1)

### Sample Input (输入样例)


10
7 9
-8 -1
-3 -1
1 4
-3 9
6 -4
7 5
6 6
-6 10
0 8


### Sample Output (输出样例)


7   // ( 9 x 2 x 6 x 7 x 1 x 5 ) % (10 + 1)


### Limitation (限制)

• 3 ≤ n ≤ 10^5
• Each coordinate of the points is an integer from (-10^5, 10^5). There are no duplicated points. Each point is selected uniformly randomly in (-10^5, 10^5) x (-10^5, 10^5).
• All points on extreme edges are regarded as extreme points and hence should be included in your solution.
• Time Limit: 2 sec
• Space Limit: 512 MB
• 3 ≤ n ≤ 10^5
• 所有点的坐标均为范围(-10^5, 10^5)内的整数，且没有重合点。每个点在(-10^5, 10^5) x (-10^5, 10^5)范围内均匀随机选取
• 极边上的所有点均被视作极点，故在输出时亦不得遗漏
• 时间限制：2 sec
• 空间限制：512 MB

### Hint (提示)

Use the CH algorithms presented in the lectures.

 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879 #include #include #include #include using namespace std; struct point {     long long x, y, id;     point() :x(0), y(0) {}     point(long long x, long long y) :x(x), y(y) {}     bool operator ==(const point& p) const {         return x == p.x && y == p.y;     } }PP; //PP: Polar Point vector points; long long area2(point p, point q, point s) {     /*     |p.x p.y 1|     |q.x q.y 1| == 2*DirectedTriangleArea(p,q,s)     |s.x s.y 1|     */     return p.x * q.y - s.x * q.y         + q.x * s.y - q.x * p.y         + s.x * p.y - p.x * s.y; } bool toLeftTest(point p, point q, point s) {     //When return value large than 0, S is on the left side of ray PQ     return area2(p, q, s) > 0; } bool toLeftTest2(point p, point q, point s) {     //When return value large than 0, S is on the left side of ray PQ     return area2(p, q, s) >= 0; } bool cmp(const point& p1, const point& p2) { // Sort according to polar angle     return PP == p1 || !(PP == p2) && toLeftTest(PP, p1, p2); } point LTL(vector& points) { //Lowest then leftmost     point ltl = points[0];     for (int i = 1; i < points.size(); i++) {         if (points[i].y < ltl.y || points[i].y == ltl.y && points[i].x < ltl.x)             ltl = points[i];     }     return ltl; } vector grahamScan() {     PP = LTL(points);     sort(points.begin(), points.end(), cmp);     vector S, T;     S.push_back(points[0]); S.push_back(points[1]);     for (int i = points.size() - 1; i > 1; i--)T.push_back(points[i]);     while (!T.empty()) {         if (toLeftTest2(S[S.size() - 2], S[S.size() - 1], T[T.size() - 1])) {             S.push_back(T[T.size() - 1]);             T.pop_back();         }         else S.pop_back();     }     return S; } int main() {     ios::sync_with_stdio(false);     long long n;     cin >> n;     for (int i = 1; i <= n; i++) {         point tmp;         cin >> tmp.x >> tmp.y;         tmp.id = i;         points.push_back(tmp);     }     vector result;     if (points.size() > 2)result = grahamScan();     else result = points;     long long res = 1;     for (int i = 0; i < result.size(); i++) {         //cout << result[i].id << endl;//debug         res = ((res % (n + 1)) * (result[i].id % (n + 1))) % (n + 1);     }     res = ((res % (n + 1)) * (result.size() % (n + 1))) % (n + 1);     cout << res; }

# 循环移位(Cycle)

### Description

Cycle shifting refers to following operation on the sting. Moving first letter to the end and keeping rest part of the string. For example, apply cycle shifting on ABCD will generate BCDA. Given any two strings, to judge if arbitrary times of cycle shifting on one string can generate the other one.

### Input

There m lines in the input, while each one consists of two strings separated by space. Each string only contains uppercase letter ‘A’~’Z’.

### Output

For each line in input, output YES in case one string can be transformed into the other by cycle shifting, otherwise output NO.

### Example

Input

AACD CDAA
ABCDEFG EFGABCD
ABCD ACBD
ABCDEFEG ABCDEE


Output

YES
YES
NO
NO


### Restrictions

0 <= m <= 5000

1 <= |S1|, |S2| <= 10^5

Time: 2 sec

Memory: 256 MB

### 限制

0 ≤ m ≤ 5000

1 ≤ |S1|, |S2| ≤ 10^5

# 重名剔除(Deduplicate)

### Description

Mr. Epicure is compiling an encyclopedia of food. He had collected a long list of candidates nominated by several belly-gods. As candidates in list are nominated by several people, duplication of name is inevitable. Mr. Epicure pay you a visit for help. He request you to remove all duplication, which is thought an easy task for you. So please hold this opportunity to be famous to all belly-gods.

### Input

1 integer in fist line to denote the length of nomination list. In following n lines, each nomination is given in each line.

### Output

All the duplicated nomination (only output once if duplication appears more multiple times), which is sorted in the order that duplication appears firstly.

### Example

Input

10
brioche
camembert
cappelletti
savarin
cheddar
cappelletti
tortellni
croissant
brioche
mapotoufu


Output

cappelletti
brioche


### Restrictions

1 < n < 6 * 10^5

All nominations are only in lowercase. No other character is included. Length of each item is not greater than 40.

Time: 2 sec

Memory: 256 MB

Hash

### 描述

Epicure先生正在编撰一本美食百科全书。为此，他已从众多的同好者那里搜集到了一份冗长的美食提名清单。既然源自多人之手，其中自然不乏重复的提名，故必须予以筛除。Epicure先生因此登门求助，并认定此事对你而言不过是“一碟小菜”，相信你不会错过在美食界扬名立万的这一良机

1 < n < 6 * 10^5

# 任务调度(Schedule)

### Description

Given initial priority setting of every task, your job is to predict the running order of a batch of tasks.

### Input

First line contains two integers, says n and m. n stands for the number of tasks in initial state. m stands for the length of predicted sequence. Every line is ended by a line break symbol. In each one of the following n lines, an integer and a string are included. This string is shorter than 8, which only contains lowercase letters and numbers. The integer is priority number and the string is the task name. The integer and string is separated by space.

### Output

At most m lines, each one contains a string. Output the name of tasks according to the order that tasks are executed. If the number of executed tasks is less than m, then output all the executed tasks.

### Example

Input

3 3
1 hello
2 world
10 test


Output

hello
hello
world


### Restrictions

0 <= n <= 4,000,000

0 <= m <= 2,000,000

0 < Priority number < 2^32

Time: 2 sec

Memory: 512 MB

Priority queue

### 限制

0 ≤ n ≤ 4,000,000

0 ≤ m ≤ 2,000,000

0 < 每个任务的初始优先级 < 2^32

# 数据结构 邓俊辉 PA#3 无线广播(Broadcast) 题解

### 输入样例

4 3
1 2
1 3
2 4


### 输出样例

1


1 ≤ n ≤ 10000

1 ≤ m ≤ 30000

BFS

# THU2017spring 2-3 Rebuild

### 输入样例1

5
1 2 4 5 3
4 2 5 1 3

### 输出样例1

4 5 2 3 1

### 输入样例2

4
2 3 1 4
4 2 1 3

### 输出样例2

-1

### 输入样例3

8
5 2 4 1 3 6 7 8
4 2 1 5 3 7 6 8

### 输出样例3

4 1 2 7 8 6 3 5

### 限制

1 <= n <= 500,000

### 提示

● 注意观察特殊节点在不同遍历序列中的位置

# THU2017spring 1-4 Hospital

### 输出

#### 输入样例

3
3 5
7 11
5 6


#### 输出样例

5
32


### 限制

1 <= n <= 300,000

### 提示

#### 一级提示

● 可以在预处理时将坐标相同的村落合并。

#### 二级提示

● 考虑医院选址向左（或向右）移动一个单位对Σwi*di的影响何时为正、何时为负。

● 注意你的程序是否能正确处理“有多个坐标权值均为最小值”的情况。

● 虽然最终选址坐标在int范围内，但计算Σwi*di的中间过程不一定在int范围内；可以使用long long，其表示的范围是[-2^63, 2^63)。

# THU2017spring 2-2 Train

### 输入样例1

5 2
1 2 3 5 4


### 输出样例1

Yes

### 输入样例2

5 5
3 1 2 4 5


### 输出样例2

No

### 限制

1 <= n <= 100,000

0 <= m <= 100,000

# 旅行商(TSP)

### Description

Shrek is a postman working in the mountain, whose routine work is sending mail to n villages. Unfortunately, road between villages is out of repair for long time, such that some road is one-way road. There are even some villages that can’t be reached from any other village. In such a case, we only hope as many villages can receive mails as possible.

Shrek hopes to choose a village A as starting point (He will be air-dropped to this location), then pass by as many villages as possible. Finally, Shrek will arrived at village B. In the travelling process, each villages is only passed by once. You should help Shrek to design the travel route.

### Input

There are 2 integers, n and m, in first line. Stand for number of village and number of road respectively.

In the following m line, m road is given by identity of villages on two terminals. From v1 to v2. The identity of village is in range [1, n].

### Output

Output maximum number of villages Shrek can pass by.

### Example

Input

4 3
1 4
2 4
4 3


Output

3


### Restrictions

1 <= n <= 1,000,000

0 <= m <= 1,000,000

These is no loop road in the input.

Time: 2 sec

Memory: 256 MB

### Hints

Topological sorting

### 描述

Shrek是一个大山里的邮递员，每天负责给所在地区的n个村庄派发信件。但杯具的是，由于道路狭窄，年久失修，村庄间的道路都只能单向通过，甚至有些村庄无法从任意一个村庄到达。这样我们只能希望尽可能多的村庄可以收到投递的信件。

Shrek希望知道如何选定一个村庄A作为起点（我们将他空投到该村庄），依次经过尽可能多的村庄，路途中的每个村庄都经过仅一次，最终到达终点村庄B，完成整个送信过程。这个任务交给你来完成。

### 限制

1 ≤ n ≤ 1,000,000

0 ≤ m ≤ 1,000,000

# 真二叉树重构(Proper Rebuild)

### Description

In general, given the preorder traversal sequence and postorder traversal sequence of a binary tree, we cannot determine the binary tree.

Figure 1

In Figure 1 for example, although they are two different binary tree, their preorder traversal sequence and postorder traversal sequence are both of the same.

But for one proper binary tree, in which each internal node has two sons, we can uniquely determine it through its given preorder traversal sequence and postorder traversal sequence.

Label n nodes in one binary tree using the integers in [1, n], we would like to output the inorder traversal sequence of a binary tree through its preorder and postorder traversal sequence.

### Input

The 1st line is an integer n, i.e., the number of nodes in one given binary tree,

The 2nd and 3rd lines are the given preorder and postorder traversal sequence respectively.

### Output

The inorder traversal sequence of the given binary tree in one line.

### Example

Input

5
1 2 4 5 3
4 5 2 3 1


Output

4 2 5 1 3


### Restrictions

For 95% of the estimation, 1 <= n <= 1,000,00

For 100% of the estimation, 1 <= n <= 4,000,000

The input sequence is a permutation of {1,2…n}, corresponding to a legal binary tree.

Time: 2 sec

Memory: 256 MB

### Hints

Figure 2

In Figure 2, observe the positions of the left and right children in preorder and postorder traversal sequence.

（图一）