Submission #20504141


Source Code Expand

Copy
using AtCoder.Internal;
using Kzrnm.Competitive;
using Kzrnm.Competitive.IO;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using static System.Math;
partial class Program
{
    partial void WriteBool(bool b) => cw.WriteLine(b ? "Yes" : "No");
    bool __ManyTestCases() => false;
    [MethodImpl(MethodImplOptions.AggressiveOptimization)]
    private object Calc()
    {
        static int CrossSign(long x1, long y1, long x2, long y2) => Sign(x1 * y2 - y1 * x2);
        int N = cr;
        var points = cr.Repeat(N).Select(cr => new PointInt(cr, cr));

        var pts = new (int x, int y, int ix)[points.Length];
        for (int i = 0; i < points.Length; i++)
            pts[i] = (points[i].x, points[i].y, i);
        Array.Sort(pts);

        var upper = new SList<(int x, int y, int ix)> { pts[0], pts[1] };
        var lower = new SList<(int x, int y, int ix)> { pts[0], pts[1] };
        for (int i = 2; i < pts.Length; i++)
        {
            while (upper.Count > 1
                && CrossSign(upper[^1].x - upper[^2].x, upper[^1].y - upper[^2].y, pts[i].x - upper[^2].x, pts[i].y - upper[^2].y) > 0)
            {
                upper.RemoveLast();
            }
            upper.Add(pts[i]);
            while (lower.Count > 1
                && CrossSign(lower[^1].x - lower[^2].x, lower[^1].y - lower[^2].y, pts[i].x - lower[^2].x, pts[i].y - lower[^2].y) < 0)
            {
                lower.RemoveLast();
            }
            lower.Add(pts[i]);
        }

        var res = new SList<int>(N);
        var used = new bool[N];
        foreach (var (_, _, ix) in upper)
        {
            used[ix] = true;
            res.Add(ix + 1);
        }
        res.Reverse();

        foreach (var (_, _, ix) in pts)
            if (!used[ix])
                res.Add(ix + 1);

        cw.WriteLines(res.AsSpan());

        return null;
    }
}
#region Expanded by https://github.com/naminodarie/SourceExpander
//LICENSE: https://github.com/naminodarie/Kzrnm.Competitive/blob/master/LICENSE
namespace AtCoder.Internal{public class SimpleList<T>:IList<T>,IReadOnlyList<T>{private T[]data;private const int DefaultCapacity=2;public SimpleList(){data=new T[DefaultCapacity];}public SimpleList(int capacity){data=new T[Math.Max(capacity,DefaultCapacity)];}public SimpleList(IEnumerable<T>collection){if(collection is ICollection<T>col){data=new T[col.Count];col.CopyTo(data,0);Count=col.Count;}else{data=new T[DefaultCapacity];foreach(var item in collection)Add(item);}}public Span<T>AsSpan()=>new Span<T>(data,0,Count);public ref T this[int index]{[MethodImpl(MethodImplOptions.AggressiveInlining)]get{if((uint)index>=(uint)Count)ThrowIndexOutOfRangeException();return ref data[index];}}public int Count{get;private set;}public void Add(T item){if((uint)Count>=(uint)data.Length)Array.Resize(ref data,data.Length<<1);data[Count++]=item;}public void RemoveLast(){if( --Count<0)ThrowIndexOutOfRangeException();}public SimpleList<T>Reverse(){Array.Reverse(data,0,Count);return this;}public SimpleList<T>Reverse(int index,int count){Array.Reverse(data,index,count);return this;}public SimpleList<T>Sort(){Array.Sort(data,0,Count);return this;}public SimpleList<T>Sort(IComparer<T>comparer){Array.Sort(data,0,Count,comparer);return this;}public SimpleList<T>Sort(int index,int count,IComparer<T>comparer){Array.Sort(data,index,count,comparer);return this;}public void Clear()=>Count=0;public bool Contains(T item)=>IndexOf(item)>=0;public int IndexOf(T item)=>Array.IndexOf(data,item,0,Count);public void CopyTo(T[]array,int arrayIndex)=>Array.Copy(data,0,array,arrayIndex,Count);public T[]ToArray()=>AsSpan().ToArray();bool ICollection<T>.IsReadOnly=>false;T IList<T>.this[int index]{get=>data[index];set=>data[index]=value;}T IReadOnlyList<T>.this[int index]{get=>data[index];}void IList<T>.Insert(int index,T item)=>throw new NotSupportedException();bool ICollection<T>.Remove(T item)=>throw new NotSupportedException();void IList<T>.RemoveAt(int index)=>throw new NotSupportedException();IEnumerator IEnumerable.GetEnumerator()=>((IEnumerable<T>)this).GetEnumerator();IEnumerator<T>IEnumerable<T>.GetEnumerator(){for(int i=0;i<Count;i++)yield return data[i];}public Span<T>.Enumerator GetEnumerator()=>AsSpan().GetEnumerator();private static void ThrowIndexOutOfRangeException()=>throw new IndexOutOfRangeException();}}
namespace Kzrnm.Competitive.IO{public partial class ConsoleWriter:IDisposable{private const int DefaultBufferSize=1<<12;public StreamWriter StreamWriter{get;}public ConsoleWriter():this(Console.OpenStandardOutput(),Console.OutputEncoding,DefaultBufferSize){}public ConsoleWriter(Stream output,Encoding encoding):this(output,encoding,DefaultBufferSize){}public ConsoleWriter(Stream output,Encoding encoding,int bufferSize){StreamWriter=new StreamWriter(output,encoding,bufferSize);}public void Flush()=>StreamWriter.Flush();public ConsoleWriter WriteLine(){StreamWriter.WriteLine();return this;}public ConsoleWriter WriteLine<T>(T obj){StreamWriter.WriteLine(obj.ToString());return this;}public ConsoleWriter WriteLineJoin<T>(IEnumerable<T>col)=>WriteMany(' ',col);public ConsoleWriter WriteLineJoin<T1,T2>((T1,T2)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2);public ConsoleWriter WriteLineJoin<T1,T2,T3>((T1,T2,T3)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3);public ConsoleWriter WriteLineJoin<T1,T2,T3,T4>((T1,T2,T3,T4)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3,tuple.Item4);public ConsoleWriter WriteLineJoin<TTuple>(TTuple tuple)where TTuple:ITuple{var col=new object[tuple.Length];for(int i=0;i<col.Length;i++)col[i]=tuple[i];return WriteLineJoin(col);}public ConsoleWriter WriteLineJoin(params object[]col)=>WriteMany(' ',col);public ConsoleWriter WriteLineJoin<T1,T2>(T1 v1,T2 v2){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v2.ToString());return this;}public ConsoleWriter WriteLineJoin<T1,T2,T3>(T1 v1,T2 v2,T3 v3){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.Write(v2.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v3.ToString());return this;}public ConsoleWriter WriteLineJoin<T1,T2,T3,T4>(T1 v1,T2 v2,T3 v3,T4 v4){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.Write(v2.ToString());StreamWriter.Write(' ');StreamWriter.Write(v3.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v4.ToString());return this;}public ConsoleWriter WriteLines<T>(IEnumerable<T>col)=>WriteMany('\n',col);public ConsoleWriter WriteLineGrid<T>(IEnumerable<IEnumerable<T>>cols){foreach(var col in cols)WriteLineJoin(col);return this;}protected ConsoleWriter WriteMany<T>(char sep,IEnumerable<T>col){var en=col.GetEnumerator();if(!en.MoveNext())goto End;StreamWriter.Write(en.Current.ToString());while(en.MoveNext()){StreamWriter.Write(sep);StreamWriter.Write(en.Current.ToString());}End:StreamWriter.WriteLine();return this;}public void Dispose()=>Flush();}}
namespace Kzrnm.Competitive.IO{public partial class ConsoleWriter{public ConsoleWriter WriteLine(ReadOnlySpan<char>obj){StreamWriter.WriteLine(obj);return this;}public ConsoleWriter WriteLineJoin<T>(Span<T>col)=>WriteMany(' ',(ReadOnlySpan<T>)col);public ConsoleWriter WriteLineJoin<T>(ReadOnlySpan<T>col)=>WriteMany(' ',col);public ConsoleWriter WriteLines<T>(Span<T>col)=>WriteMany('\n',(ReadOnlySpan<T>)col);public ConsoleWriter WriteLines<T>(ReadOnlySpan<T>col)=>WriteMany('\n',col);protected ConsoleWriter WriteMany<T>(char sep,ReadOnlySpan<T>col){var en=col.GetEnumerator();if(!en.MoveNext())return this;StreamWriter.Write(en.Current.ToString());while(en.MoveNext()){StreamWriter.Write(sep);StreamWriter.Write(en.Current.ToString());}StreamWriter.WriteLine();return this;}}}
namespace Kzrnm.Competitive.IO{public struct PropertyRepeatReader{internal readonly PropertyConsoleReader cr;internal readonly int count;internal PropertyRepeatReader(PropertyConsoleReader cr,int count){this.cr=cr;this.count=count;}public string[]Line{get{var arr=new string[count];for(var i=0;i<count;i++)arr[i]=cr.Line;return arr;}}public string[]String{get{var arr=new string[count];for(var i=0;i<count;i++)arr[i]=cr.String;return arr;}}public string[]Ascii{get{var arr=new string[count];for(var i=0;i<count;i++)arr[i]=cr.Ascii;return arr;}}public int[]Int{get{var arr=new int[count];for(var i=0;i<count;i++)arr[i]=cr.Int;return arr;}}public int[]Int0{get{var arr=new int[count];for(var i=0;i<count;i++)arr[i]=cr.Int0;return arr;}}public long[]Long{get{var arr=new long[count];for(var i=0;i<count;i++)arr[i]=cr.Long;return arr;}}public long[]Long0{get{var arr=new long[count];for(var i=0;i<count;i++)arr[i]=cr.Long0;return arr;}}public ulong[]ULong{get{var arr=new ulong[count];for(var i=0;i<count;i++)arr[i]=cr.ULong;return arr;}}public ulong[]ULong0{get{var arr=new ulong[count];for(var i=0;i<count;i++)arr[i]=cr.ULong0;return arr;}}public double[]Double{get{var arr=new double[count];for(var i=0;i<count;i++)arr[i]=cr.Double;return arr;}}public decimal[]Decimal{get{var arr=new decimal[count];for(var i=0;i<count;i++)arr[i]=cr.Decimal;return arr;}}public static implicit operator string[](PropertyRepeatReader rr)=>rr.Ascii;public static implicit operator int[](PropertyRepeatReader rr)=>rr.Int;public static implicit operator long[](PropertyRepeatReader rr)=>rr.Long;public static implicit operator ulong[](PropertyRepeatReader rr)=>rr.ULong;public static implicit operator double[](PropertyRepeatReader rr)=>rr.Double;public static implicit operator decimal[](PropertyRepeatReader rr)=>rr.Decimal;}public static class PRepeatEx{public static PropertyRepeatReader Repeat(this PropertyConsoleReader cr,int count)=>new PropertyRepeatReader(cr,count);}}
namespace Kzrnm.Competitive.IO{public static class PropertyRepeatReaderSelect{public static T[]Select<T>(this PropertyRepeatReader r,Func<PropertyConsoleReader,T>factory){var arr=new T[r.count];for(var i=0;i<r.count;i++)arr[i]=factory(r.cr);return arr;}public static T[]Select<T>(this PropertyRepeatReader r,Func<PropertyConsoleReader,int,T>factory){var arr=new T[r.count];for(var i=0;i<r.count;i++)arr[i]=factory(r.cr,i);return arr;}}}
namespace Kzrnm.Competitive{public class SList<T>:SimpleList<T>{public SList():base(){}public SList(int capacity):base(capacity){}public SList(IEnumerable<T>collection):base(collection){}}}
internal partial class Program{static void Main()=>new Program(new PropertyConsoleReader(),new ConsoleWriter()).Run();public PropertyConsoleReader cr;public ConsoleWriter cw;public Program(PropertyConsoleReader r,ConsoleWriter w){this.cr=r;this.cw=w;CultureInfo.CurrentCulture=CultureInfo.InvariantCulture;}public void Run(){int Q=1;if(__ManyTestCases())Q=cr;for(;Q>0;Q--){var res=Calc();if(res is double d)cw.WriteLine(d.ToString("0.####################",CultureInfo.InvariantCulture));else if(res is bool b)WriteBool(b);else if(res!=null)cw.WriteLine(res.ToString());}cw.Flush();}partial void WriteBool(bool b);object Calc(Program dum=null)=>dum;bool __ManyTestCases(Program dum=null)=>false;}
namespace Kzrnm.Competitive{public readonly struct PointInt:IEquatable<PointInt>,IComparable<PointInt>{public readonly int x;public readonly int y;public PointInt(int x,int y){this.x=x;this.y=y;}public void Deconstruct(out int v1,out int v2){v1=x;v2=y;}public static implicit operator PointInt((int x,int y)tuple)=>new PointInt(tuple.x,tuple.y);public double Distance(PointInt other)=>Math.Sqrt(Distance2(other));public long Distance2(PointInt other){var p=other-this;return(long)p.x*p.x+(long)p.y*p.y;}public long Inner(PointInt other)=>(long)x*other.x+(long)y*other.y;public long Cross(PointInt other)=>(long)x*other.y-(long)y*other.x;public static PointInt operator+(PointInt a,PointInt b)=>new PointInt(a.x+b.x,a.y+b.y);public static PointInt operator-(PointInt a,PointInt b)=>new PointInt(a.x-b.x,a.y-b.y);public int CompareTo(PointInt other)=>Math.Atan2(this.y,this.x).CompareTo(Math.Atan2(other.y,other.x));public bool Equals(PointInt other)=>this.x==other.x&&this.y==other.y;public override bool Equals(object obj)=>obj is PointInt p&&this.Equals(p);public override int GetHashCode()=>HashCode.Combine(x,y);public override string ToString()=>$"{x} {y}";public static bool operator==(PointInt left,PointInt right)=>left.Equals(right);public static bool operator!=(PointInt left,PointInt right)=>!left.Equals(right);static int CrossSign(long x1,long y1,long x2,long y2)=>Math.Sign(x1*y2-y1*x2);public static int[]ConvexHull(PointInt[]points){var pts=new(int x,int y,int ix)[points.Length];for(int i=0;i<points.Length;i++)pts[i]=(points[i].x,points[i].y,i);Array.Sort(pts);var upper=new SimpleList<(int x,int y,int ix)>{pts[0],pts[1]};var lower=new SimpleList<(int x,int y,int ix)>{pts[0],pts[1]};for(int i=2;i<pts.Length;i++){while(upper.Count>1&&CrossSign(upper[^1].x-upper[^2].x,upper[^1].y-upper[^2].y,pts[i].x-upper[^2].x,pts[i].y-upper[^2].y)>0){upper.RemoveLast();}upper.Add(pts[i]);while(lower.Count>1&&CrossSign(lower[^1].x-lower[^2].x,lower[^1].y-lower[^2].y,pts[i].x-lower[^2].x,pts[i].y-lower[^2].y)<0){lower.RemoveLast();}lower.Add(pts[i]);}var res=new int[upper.Count+lower.Count-2];var span=upper.AsSpan();for(int i=0;i<span.Length;i++)res[res.Length-i-1]=span[i].ix;span=lower.AsSpan()[1..^1];for(int i=0;i<span.Length;i++)res[i]=span[i].ix;return res;}}}
namespace Kzrnm.Competitive.IO{using static MethodImplOptions;public class PropertyConsoleReader{private const int BufSize=1<<12;private readonly Stream input;private readonly Encoding encoding;internal readonly byte[]buffer=new byte[BufSize];internal int pos=0;internal int len=0;public PropertyConsoleReader():this(Console.OpenStandardInput(),Console.InputEncoding){}public PropertyConsoleReader(Stream input,Encoding encoding){this.input=input;this.encoding=encoding;}[MethodImpl(AggressiveInlining)]protected internal byte Read(){if( ++pos>=len){if((len=input.Read(buffer,0,buffer.Length))<=0){buffer[0]=10;}pos=0;}return buffer[pos];}public int Int{[MethodImpl(AggressiveInlining)]get{int res=0;bool neg=false;byte b;do{b=Read();if(b=='-')neg=true;}while(b<'0');do{res=res*10+(b^'0');b=Read();}while('0'<=b);return neg?-res:res;}}public int Int0{[MethodImpl(AggressiveInlining)]get=>Int-1;}public long Long{[MethodImpl(AggressiveInlining)]get{long res=0;bool neg=false;byte b;do{b=Read();if(b=='-')neg=true;}while(b<'0');do{res=res*10+(b^'0');b=Read();}while('0'<=b);return neg?-res:res;}}public long Long0{[MethodImpl(AggressiveInlining)]get=>Long-1;}public ulong ULong{[MethodImpl(AggressiveInlining)]get{ulong res=0;byte b;do b=Read();while(b<'0');do{res=res*10+(b^(ulong)'0');b=Read();}while('0'<=b);return res;}}public ulong ULong0{[MethodImpl(AggressiveInlining)]get=>ULong-1;}public string String{[MethodImpl(AggressiveInlining)]get{var sb=new List<byte>();;byte b;do b=Read();while(b<=' ');do{sb.Add(b);b=Read();}while(' '<b);return encoding.GetString(sb.ToArray());}}public string Ascii{[MethodImpl(AggressiveInlining)]get{var sb=new StringBuilder();byte b;do b=Read();while(b<=' ');do{sb.Append((char)b);b=Read();}while(' '<b);return sb.ToString();}}public string Line{[MethodImpl(AggressiveInlining)]get{var sb=new List<byte>();byte b;do b=Read();while(b<=' ');do{sb.Add(b);b=Read();}while(b!='\n'&&b!='\r');return encoding.GetString(sb.ToArray());}}public char Char{[MethodImpl(AggressiveInlining)]get{byte b;do b=Read();while(b<=' ');return(char)b;}}public double Double{[MethodImpl(AggressiveInlining)]get{return double.Parse(Ascii);}}public decimal Decimal{[MethodImpl(AggressiveInlining)]get{return decimal.Parse(Ascii);}}[MethodImpl(AggressiveInlining)]public static implicit operator int(PropertyConsoleReader cr)=>cr.Int;[MethodImpl(AggressiveInlining)]public static implicit operator long(PropertyConsoleReader cr)=>cr.Long;[MethodImpl(AggressiveInlining)]public static implicit operator ulong(PropertyConsoleReader cr)=>cr.ULong;[MethodImpl(AggressiveInlining)]public static implicit operator double(PropertyConsoleReader cr)=>cr.Double;[MethodImpl(AggressiveInlining)]public static implicit operator decimal(PropertyConsoleReader cr)=>cr.Decimal;[MethodImpl(AggressiveInlining)]public static implicit operator string(PropertyConsoleReader cr)=>cr.Ascii;}}
#endregion Expanded by https://github.com/naminodarie/SourceExpander

Submission Info

Submission Time
Task B - Jumps
User naminodarie
Language C# (.NET Core 3.1.201)
Score 0
Code Size 16466 Byte
Status IE