所需基础

计算几何 - 凸包、了解 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" 指最终确定的升序序列。

题面

Flip Game
Time Limit: 1000MS Memory Limit: 65536K

Description

Flip game is played on a rectangular 4x4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it's black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules:

1. Choose any one of the 16 pieces.
2. Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).

Consider the following position as an example:

bwbw
wwww
bbwb
bwwb
Here "b" denotes pieces lying their black side up and "w" denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become:

bwbw
bwww
wwwb
wwwb
The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.

Input

The input consists of 4 lines with 4 characters "w" or "b" each that denote game field position.

Output

Write to the output file a single integer number - the minimum number of rounds needed to achieve the goal of the game from the given position. If the goal is initially achieved, then write 0. If it's impossible to achieve the goal, then write the word "Impossible" (without quotes).

Sample Input

bwwb
bbwb
bwwb
bwww

Sample Output

4

Source

Northeastern Europe 2000