#495017 (C#(csc)) No.1041 直線大学

提出ソース

結果

問題	No.1041 直線大学
ユーザー	fairy_lettuce
提出日時	2020-06-11 01:43:49
言語	C#(csc) (csc 3.9.0)
結果	AC
実行時間	29 ms / 2,000 ms
コード長	9,881 bytes
コンパイル時間	866 ms
コンパイル使用メモリ	112,768 KB
実行使用メモリ	18,688 KB
最終ジャッジ日時	2024-04-28 00:16:30
合計ジャッジ時間	2,746 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	25 ms 18,304 KB
testcase_01	AC	26 ms 18,688 KB
testcase_02	AC	25 ms 18,432 KB
testcase_03	AC	26 ms 18,304 KB
testcase_04	AC	26 ms 18,176 KB
testcase_05	AC	25 ms 18,688 KB
testcase_06	AC	26 ms 18,176 KB
testcase_07	AC	26 ms 18,304 KB
testcase_08	AC	25 ms 18,432 KB
testcase_09	AC	25 ms 18,176 KB
testcase_10	AC	27 ms 18,176 KB
testcase_11	AC	25 ms 18,304 KB
testcase_12	AC	27 ms 18,304 KB
testcase_13	AC	26 ms 18,176 KB
testcase_14	AC	28 ms 18,292 KB
testcase_15	AC	26 ms 18,416 KB
testcase_16	AC	29 ms 18,356 KB
testcase_17	AC	28 ms 18,432 KB
testcase_18	AC	27 ms 18,420 KB
testcase_19	AC	28 ms 18,292 KB
testcase_20	AC	26 ms 18,432 KB
testcase_21	AC	27 ms 18,288 KB
testcase_22	AC	26 ms 18,304 KB
testcase_23	AC	26 ms 18,484 KB
testcase_24	AC	27 ms 18,404 KB
testcase_25	AC	27 ms 18,176 KB
testcase_26	AC	25 ms 18,432 KB
testcase_27	AC	27 ms 18,432 KB
testcase_28	AC	25 ms 18,560 KB
testcase_29	AC	27 ms 18,176 KB
testcase_30	AC	25 ms 18,176 KB
testcase_31	AC	26 ms 18,432 KB
testcase_32	AC	26 ms 18,432 KB
testcase_33	AC	25 ms 18,048 KB
testcase_34	AC	24 ms 18,432 KB
testcase_35	AC	25 ms 18,304 KB
testcase_36	AC	24 ms 18,304 KB
testcase_37	AC	24 ms 18,432 KB
testcase_38	AC	27 ms 18,160 KB
testcase_39	AC	26 ms 18,176 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

raw source code

using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO.Pipes;

namespace AtCoder.Contest.A
{
	static class Program
	{
		public static void Main(string[] args)
		{
			var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
			Console.SetOut(sw);

			var cin = new Scanner();

			int n = cin.NextInt();
			var p = new List<Pair<int, int>>();
            for (int i = 0; i < n; i++)
            {
				p.Add(new Pair<int, int>(cin.NextInt(), cin.NextInt()));
			}
			p.Sort();
			int ans = 0;
			var dic = new Dictionary<long, int>();
            for (int i = 0; i < n; i++)
            {
                for (int j = i + 1; j < n; j++)
                {
					int vx = p[j].First - p[i].First;
					int vy = p[j].Second - p[i].Second;
					ModInt slope = vx != 0 ? (ModInt)(vy) / vx : 106;
					ModInt intersept = slope != 106 ? p[i].Second - slope * p[i].First : p[i].First;
					long key = (long)slope * (long)ModInt.MOD + (long)intersept;
					if (dic.ContainsKey(key)) dic[key]++;
					else dic.Add(key, 1);
				}
            }
			var l = new List<int>();
            for (int i = 0; i < 105; i++)
            {
				l.Add(i * (i - 1) / 2);
            }
            foreach (var e in dic)
            {
				var now = l.LowerBound(e.Value);
				if (ans < now) ans = now;
            }
            Console.WriteLine(ans);

			Console.Out.Flush();
		}
	}

	static class BinarySearch
	{
		public static int UpperBound<T>(T[] array, T value) => UpperBound(array, 0, array.Length - 1, value, Comparer<T>.Default);

		public static int UpperBound<T>(T[] array, T value, Comparer<T> comparer) => UpperBound(array, 0, array.Length - 1, value, comparer);

		public static int UpperBound<T>(T[] array, int index, int length, T value) => UpperBound(array, index, length, value, Comparer<T>.Default);

		public static int UpperBound<T>(T[] array, int index, int length, T value, Comparer<T> comparer)
		{
			var l = index;
			var r = l + length - 1;
			while (l <= r)
			{
				var mid = l + (r - l) / 2;
				var res = comparer.Compare(array[mid], value);
				if (res <= 0) l = mid + 1;
				else r = mid - 1;
			}
			return l;
		}

		public static int UpperBound<T>(this List<T> list, T item) => list.UpperBound(0, list.Count, item, Comparer<T>.Default);

		public static int UpperBound<T>(this List<T> list, T item, Comparer<T> comparer) => list.UpperBound(0, list.Count, item, comparer);

		public static int UpperBound<T>(this List<T> list, int index, int count, T item, Comparer<T> comparer)
		{
			var l = index;
			var r = l + count - 1;
			while (l <= r)
			{
				var mid = l + (r - l) / 2;
				var res = comparer.Compare(list[mid], item);
				if (res <= 0) l = mid + 1;
				else r = mid - 1;
			}
			return l;
		}

		public static int LowerBound<T>(T[] array, T value) => LowerBound(array, 0, array.Length - 1, value, Comparer<T>.Default);

		public static int LowerBound<T>(T[] array, T value, Comparer<T> comparer) => LowerBound(array, 0, array.Length - 1, value, comparer);

		public static int LowerBound<T>(T[] array, int index, int length, T value) => LowerBound(array, index, length, value, Comparer<T>.Default);

		public static int LowerBound<T>(T[] array, int index, int length, T value, Comparer<T> comparer)
		{
			var l = index;
			var r = l + length - 1;
			while (l <= r)
			{
				var mid = l + (r - l) / 2;
				var res = comparer.Compare(array[mid], value);
				if (res == -1) l = mid + 1;
				else r = mid - 1;
			}
			return l;
		}

		public static int LowerBound<T>(this List<T> list, T item) => list.LowerBound(0, list.Count, item, Comparer<T>.Default);

		public static int LowerBound<T>(this List<T> list, T item, Comparer<T> comparer) => list.LowerBound(0, list.Count, item, comparer);

		public static int LowerBound<T>(this List<T> list, int index, int count, T item, Comparer<T> comparer)
		{
			var l = index;
			var r = l + count - 1;
			while (l <= r)
			{
				var mid = l + (r - l) / 2;
				var res = comparer.Compare(list[mid], item);
				if (res == -1) l = mid + 1;
				else r = mid - 1;
			}
			return l;
		}
	}

	public struct ModInt : IComparable<ModInt>, IEquatable<ModInt>
	{
		public static long MOD = 1000000007;

		private readonly long num;

		public ModInt(long n) { num = n; }

		public override string ToString() => num.ToString();

		public static ModInt operator +(ModInt l, ModInt r)
		{
			long x = l.num + r.num;
			if (x >= MOD) x -= MOD;
			return new ModInt(x);
		}
		public static ModInt operator -(ModInt l, ModInt r)
		{
			long x = l.num - r.num;
			if (x < 0) x += MOD;
			return new ModInt(x);
		}
		public static ModInt operator *(ModInt l, ModInt r) => new ModInt((l.num * r.num) % MOD);
		public static ModInt operator /(ModInt l, ModInt r) => l * r.Inverse();

		public static ModInt operator ++(ModInt x)
		{
			var tmp = x + new ModInt(1);
			return tmp;
		}
		public static ModInt operator --(ModInt x)
		{
			var tmp = x - new ModInt(1);
			return tmp;
		}

		public static bool operator >(ModInt l, ModInt r) => l.CompareTo(r) > 0;
		public static bool operator <(ModInt l, ModInt r) => l.CompareTo(r) < 0;
		public static bool operator >=(ModInt l, ModInt r) => l.CompareTo(r) >= 0;
		public static bool operator <=(ModInt l, ModInt r) => l.CompareTo(r) <= 0;
		public static bool operator ==(ModInt l, ModInt r) => l.Equals(r);
		public static bool operator !=(ModInt l, ModInt r) => !l.Equals(r);

		public static implicit operator long(ModInt x) => x.num;
		public static implicit operator ModInt(long n)
		{
			n %= MOD;
			if (n < 0) n += MOD;
			return new ModInt(n);
		}

		public ModInt Inverse() => Inverse(this, MOD);
		public static ModInt Inverse(ModInt x) => Inverse(x.num, MOD);
		public static long Inverse(long x, long m)
		{
			if (x % m == 0) throw new DivideByZeroException();
			long a = x, b = m, u = 1, v = 0;
			while (b > 0)
			{
				long t = a / b;

				a -= t * b;
				long p = a; a = b; b = p;   // swap(a, b);

				u -= t * v;
				p = u; u = v; v = p;        // swap(u, v);
			}
			u %= m;
			if (u < 0) u += m;
			return u;
		}

		public static ModInt Pow(ModInt x, long n) => Pow(x.num, n);
		public static ModInt Pow(long x, long n)
		{
			if (n == 0) return x;
			long now = 1;
			for (n %= MOD - 1; n > 0; n /= 2, x = x * x % MOD)
			{
				if (n % 2 == 1) now = now * x % MOD;
			}
			return new ModInt(now);
		}

		public int CompareTo(ModInt x)
		{
			if (num == x.num) return 0;
			if (num > x.num) return 1;
			return -1;
		}

		public bool Equals(ModInt x) => num == x.num;

		public override bool Equals(object obj) => obj is ModInt m && num == m.num;

		public override int GetHashCode()
		{
			return HashCode.Combine(num);
		}

	}

	public class Pair<T, U> : IComparable, IEquatable<Pair<T, U>> where T : IComparable<T>, IEquatable<T> where U : IComparable<U>, IEquatable<U>
	{
		public T First { get; set; }
		public U Second { get; set; }

		public Pair(T first, U second)
		{
			First = first;
			Second = second;
		}

		public int CompareTo(object obj)
		{
			Pair<T, U> castedObj = (Pair<T, U>)obj;
			int x = First.CompareTo(castedObj.First);
			if (x != 0) return x;
			else return Second.CompareTo(castedObj.Second);
		}

		public static bool operator ==(Pair<T, U> x, Pair<T, U> y) => x.CompareTo(y) == 0;

		public static bool operator !=(Pair<T, U> x, Pair<T, U> y) => x.CompareTo(y) != 0;

		public static bool operator <(Pair<T, U> x, Pair<T, U> y) => x.CompareTo(y) == 1;

		public static bool operator >(Pair<T, U> x, Pair<T, U> y) => x.CompareTo(y) == -1;

		public static bool operator <=(Pair<T, U> x, Pair<T, U> y) => x.CompareTo(y) > 0;

		public static bool operator >=(Pair<T, U> x, Pair<T, U> y) => x.CompareTo(y) < 0;

		public bool Equals(Pair<T, U> x) => First.Equals(x.First) && Second.Equals(x.Second);

		public override bool Equals(object obj)
		{
			return obj is Pair<T, U> pair &&
				   EqualityComparer<T>.Default.Equals(First, pair.First) &&
				   EqualityComparer<U>.Default.Equals(Second, pair.Second);
		}

		public override int GetHashCode()
		{
			unchecked
			{
				var hashCode = 405212230;
				hashCode = hashCode * -1521134295 + EqualityComparer<T>.Default.GetHashCode(First);
				hashCode = hashCode * -1521134295 + EqualityComparer<U>.Default.GetHashCode(Second);
				return hashCode;
			}
		}
	}

	public static partial class Calc
	{
		public static void Swap<T>(ref T x, ref T y)
		{
			T z;
			z = x;
			x = y;
			y = z;
		}

		public static long GCD(long a, long b)
		{
			a = Math.Abs(a);
			b = Math.Abs(b);
			while (a > 0)
			{
				a %= b;
				Swap(ref a, ref b);
			}
			return a;
		}

		public static long LCM(long a, long b) => (a / GCD(a, b) * b);
	}

	class Scanner
	{
		string[] s;
		int i;

		char[] cs = new char[] { ' ' };

		public Scanner()
		{
			s = new string[0];
			i = 0;
		}

		public string Next()
		{
			if (i < s.Length) return s[i++];
			string st = Console.ReadLine();
			while (st == "") st = Console.ReadLine();
			s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
			if (s.Length == 0) return Next();
			i = 0;
			return s[i++];
		}

		public int NextInt()
		{
			return int.Parse(Next());
		}

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextInt() + add;
			}
			return Array;
		}

		public long NextLong()
		{
			return long.Parse(Next());
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextLong() + add;
			}
			return Array;
		}

		public double NextDouble()
		{
			return double.Parse(Next());
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = NextDouble() + add;
			}
			return Array;
		}
	}
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード