题面

MoutainTop
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description
金石山脉有n个山峰，一字排开，从西向东依次编号为1, 2, 3, ……, n。编号为i的山峰高度为hi。每个山峰的高度两两不同
小木示从西向东依次爬过这n个山峰，到每一个山峰的山顶的时候，他都会往西边眺望，并且会记录下自己能看到的山峰的个数。
（比如说小木示现在在4号山峰，前四号山峰的高度分别为9,4,5,1。他现在能看到的山峰个数就是2,因为第二个山峰被第三个山峰挡住了）
严格的来说，小木示在i位置的时候，对于一个山峰j (j < i)，如果不存在一个山峰k满足hj < hk (j < k < i)。则山峰j是可见的。
小木示把自己记录的山峰的个数加和作为这次爬山的快乐值，现在给你n个山峰的高度，求小木示的快乐值。

Input
多组输入，首先输入一个n（1<=n<=10^6）,表示山峰的个数。 接下来一行n个数，表示对应山峰的山峰的高度(1<=h<=10^6)。

Output
输出小木示的快乐值

Example Input
4
1 6 5 1

Example Output
4

Author
JueChen

所需基础

计算几何 - 凸包、了解 Graham's Scan 算法及其极角序实现。

概述

Graham's Scan 算法的水平序实现是不同于「极角序」的另一种实现方式，它将平面点集按照水平序排序，即按 y 坐标排序，相同时再按 x 坐标排序，之后进行扫描来求得凸包。

题面

飞花的传送门
Time Limit: 1000ms Memory limit: 65536K

题目描述
飞花壕最近手头比较宽裕，所以想买两个传送门来代步（夏天太热，实在是懒得走路）。平面上有N个传送门，飞花壕想要挑两个距离最远的传送门带回家（距离为欧几里得距离，即两点之间直线距离）。

请你帮他算一算他所挑选的最远的两个传送门有多远。

输入
多组输入。

对于每组输入，第一行输入一个整数N（2 <= N <= 50000），接下来从第2行到第N+1行，每行两个整数（Xi，Yi），代表第i个传送门的坐标（-1000000 <= Xi , Yi <= 1000000）。

数据为随机生成。

输出
输出一个整数，代表飞花壕要挑选的两个传送门的距离的平方。

示例输入
4
0 0
0 1
1 1
1 0

示例输出
2

提示

来源
GLSilence

题目链接

题目大意

给定一个二维迷宫， "#" 表示不可走的位置，“.” 表示可走的位置，起点为 “S”，终点为 “E”。问左手扶墙走、右手扶墙走和最短路线的步数各是多少。

题目链接

题目翻译

描述

一个升序序列中不同元素之间可以用带小于号的关系式来从小到大排列元素。例如，有序序列 A, B, C, D 中包含关系 A < B, B < C 和 C < D。在本题中，我们会给你一个形如 "A < B" 的关系集合，请你决定由此构成的有序序列是否唯一。

输入

输入包含多组实例。每组实例的第一行包含两个正整数 n, m，前者表示待排序对象的数量，2 <= n <= 26，待排序对象是字母表中前 n 个大写字母；后者表示题目实例中给出的 "A < B" 形式的关系数量。接下来有 m 行，每行包含一对关系，每对关系由三个字符组成：一个大写字母、一个小于号和另一个大写字母。不会出现超出前 n 个大写字母的数据。当 n = m = 0 时输入结束。

输出

对于每组测试实例，输出一行，每行会是以下三种情况之一：

Sorted sequence determined after xxx relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.

其中 "xxx" 指有序序列被确定或被证明矛盾时已处理的关系数量，"yyy...y" 指最终确定的升序序列。