結果
| 問題 | No.1041 直線大学 |
| ユーザー |
 fairy_lettuce
|
| 提出日時 | 2020-06-11 01:39:06 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,853 bytes |
| コンパイル時間 | 1,019 ms |
| コンパイル使用メモリ | 122,876 KB |
| 実行使用メモリ | 28,492 KB |
| 最終ジャッジ日時 | 2024-06-23 22:19:19 |
| 合計ジャッジ時間 | 3,576 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 34 WA * 3 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
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 = p[i].Second - slope * 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;}}}