using System;
using System.Collections.Generic;
using System.Linq;
// Q068 凸包 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_A&lang=jp
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("7");
WillReturn.Add("2 1");
WillReturn.Add("0 0");
WillReturn.Add("1 2");
WillReturn.Add("2 2");
WillReturn.Add("4 2");
WillReturn.Add("1 3");
WillReturn.Add("3 3");
//5
//0 0
//2 1
//4 2
//3 3
//1 3
}
else if (InputPattern == "Input2") {
WillReturn.Add("3");
WillReturn.Add("0 0");
WillReturn.Add("1 0");
WillReturn.Add("-1 2");
//3
//0 0
//1 0
//-1 2
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
struct PointDef
{
internal double X;
internal double Y;
}
static void Main()
{
List<string> InputList = GetInputList();
double[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(X => double.Parse(X)).ToArray();
var XYInfoList = new List<PointDef>();
foreach (string EachStr in InputList.Skip(1)) {
SplitAct(EachStr);
PointDef WillAdd;
WillAdd.X = wkArr[0];
WillAdd.Y = wkArr[1];
XYInfoList.Add(WillAdd);
}
List<PointDef> AndrewScanResult = AndrewScan(XYInfoList);
Console.WriteLine(AndrewScanResult.Count);
var Query = AndrewScanResult.OrderBy(pX => pX.Y).ThenBy(pX => pX.X).First();
int StaInd = AndrewScanResult.FindIndex(pX => pX.X == Query.X && pX.Y == Query.Y);
int UB = AndrewScanResult.Count - 1;
for (int I = StaInd; I <= UB; I++) {
Console.WriteLine("{0} {1}", AndrewScanResult[I].X, AndrewScanResult[I].Y);
}
for (int I = 0; I < StaInd; I++) {
Console.WriteLine("{0} {1}", AndrewScanResult[I].X, AndrewScanResult[I].Y);
}
}
// アンドリューのアルゴリズムで凸包の座標のListを返す
static List<PointDef> AndrewScan(List<PointDef> pPointList)
{
if (pPointList.Count < 3) return pPointList;
// X,Yを基準にソート
PointDef[] SortedPointArr = pPointList.OrderBy(pX => pX.X).ThenBy(pX => pX.Y).ToArray();
int UB = SortedPointArr.GetUpperBound(0);
// 凸包の上部の座標のList
var UpperList = new List<PointDef>();
// Xが小さいのものから2つを追加
UpperList.Add(SortedPointArr[0]);
UpperList.Add(SortedPointArr[1]);
// 凸包の下部の座標のList
var LowerList = new List<PointDef>();
// Xが大きいのものから2つを追加
LowerList.Add(SortedPointArr[UB]);
LowerList.Add(SortedPointArr[UB - 1]);
// 凸包の上部を生成
for (int I = 2; I <= UB; I++) {
for (int J = UpperList.Count; 2 <= J; J--) {
if (CCW(UpperList[J - 2], UpperList[J - 1], SortedPointArr[I]) == 1) {
UpperList.RemoveAt(UpperList.Count - 1);
}
else {
break;
}
}
UpperList.Add(SortedPointArr[I]);
}
// 凸包の下部を生成
for (int I = UB - 2; 0 <= I; I--) {
for (int J = LowerList.Count; 2 <= J; J--) {
if (CCW(LowerList[J - 2], LowerList[J - 1], SortedPointArr[I]) == 1) {
LowerList.RemoveAt(LowerList.Count - 1);
}
else {
break;
}
}
LowerList.Add(SortedPointArr[I]);
}
// 凸法の点の列を生成
LowerList.Reverse();
for (int I = UpperList.Count - 2; 1 <= I; I--) {
LowerList.Add(UpperList[I]);
}
return LowerList;
}
static int CCW(PointDef pPointA, PointDef pPointB, PointDef pPointC)
{
const int COUNTER_CLOCKWISE = 1;
const int CLOCKWISE = -1;
const int ONLINE_BACK = 2;
const int ONLINE_FRONT = -2;
const int ON_SEGMENT = 0;
PointDef VectorA = SetVector(pPointA, pPointB);
PointDef VectorB = SetVector(pPointA, pPointC);
// 外積 A*Bを求める
double Cross = DeriveCross(VectorA, VectorB);
// Aの半時計回りの方向にBが存在する
if (Cross > 0) {
return COUNTER_CLOCKWISE;
}
// Aの時計回りの方向にBが存在する
if (Cross < 0) {
return CLOCKWISE;
}
// 3点が1直線にある場合
// 内積がマイナスなら、ベクトルの向きは反対
double Dot = DeriveDot(VectorA, VectorB);
if (Dot < 0) {
return ONLINE_BACK;
}
double NormA = DeriveNorm(VectorA);
double NormB = DeriveNorm(VectorB);
if (NormA < NormB) {
return ONLINE_FRONT;
}
return ON_SEGMENT;
}
// 始点と終点の座標を引数として、始点から終点へのベクトルを返す
static PointDef SetVector(PointDef pStaPoint, PointDef pEndPoint)
{
PointDef WillReturn;
WillReturn.X = pEndPoint.X - pStaPoint.X;
WillReturn.Y = pEndPoint.Y - pStaPoint.Y;
return WillReturn;
}
// 内積を求める
static double DeriveDot(PointDef pVector1, PointDef pVector2)
{
return pVector1.X * pVector2.X + pVector1.Y * pVector2.Y;
}
// 外積を求める
static double DeriveCross(PointDef pVector1, PointDef pVector2)
{
return pVector1.X * pVector2.Y - pVector1.Y * pVector2.X;
}
// ベクトルの大きさを求める
static double DeriveABS(PointDef pVector)
{
double wkNorm = DeriveNorm(pVector);
double wkSqrt = Math.Sqrt(wkNorm);
return wkSqrt;
}
// ベクトルのNormを求める
static double DeriveNorm(PointDef pVector)
{
return pVector.X * pVector.X + pVector.Y * pVector.Y;
}
}