結果

問題 No.1041 直線大学
ユーザー fgwiebfaoishfgwiebfaoish
提出日時 2020-05-02 07:03:02
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 52 ms / 2,000 ms
コード長 8,916 bytes
コンパイル時間 2,445 ms
コンパイル使用メモリ 116,728 KB
実行使用メモリ 20,352 KB
最終ジャッジ日時 2024-11-16 07:59:16
合計ジャッジ時間 4,450 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 29 ms
19,072 KB
testcase_01 AC 29 ms
19,072 KB
testcase_02 AC 28 ms
19,072 KB
testcase_03 AC 28 ms
18,944 KB
testcase_04 AC 30 ms
19,328 KB
testcase_05 AC 29 ms
19,200 KB
testcase_06 AC 30 ms
19,200 KB
testcase_07 AC 30 ms
19,200 KB
testcase_08 AC 31 ms
19,328 KB
testcase_09 AC 31 ms
19,200 KB
testcase_10 AC 47 ms
20,096 KB
testcase_11 AC 46 ms
20,096 KB
testcase_12 AC 48 ms
20,352 KB
testcase_13 AC 32 ms
19,200 KB
testcase_14 AC 42 ms
19,768 KB
testcase_15 AC 33 ms
19,188 KB
testcase_16 AC 38 ms
19,680 KB
testcase_17 AC 29 ms
19,328 KB
testcase_18 AC 34 ms
19,456 KB
testcase_19 AC 41 ms
19,676 KB
testcase_20 AC 29 ms
18,816 KB
testcase_21 AC 37 ms
19,564 KB
testcase_22 AC 29 ms
18,944 KB
testcase_23 AC 50 ms
19,960 KB
testcase_24 AC 42 ms
19,812 KB
testcase_25 AC 36 ms
19,456 KB
testcase_26 AC 30 ms
19,328 KB
testcase_27 AC 33 ms
19,072 KB
testcase_28 AC 29 ms
18,944 KB
testcase_29 AC 28 ms
18,816 KB
testcase_30 AC 30 ms
18,944 KB
testcase_31 AC 28 ms
18,816 KB
testcase_32 AC 28 ms
18,944 KB
testcase_33 AC 28 ms
18,816 KB
testcase_34 AC 29 ms
19,072 KB
testcase_35 AC 29 ms
18,816 KB
testcase_36 AC 28 ms
19,072 KB
testcase_37 AC 29 ms
18,816 KB
testcase_38 AC 52 ms
20,224 KB
testcase_39 AC 33 ms
19,456 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
using static Exg;
static class Program{
	const int mod=(int)1e9+7;
	const double eps=1e-11;
	static void Main(){
		Sc sc=new Sc();
		var n=sc.I;
		var hs=new Dictionary<string,int>();
		var pa=new Pair[n];
		int ans=0;
		for(int i = 0;i<n;i++) {
			pa[i]=new Pair(sc.Da);
			for(int j = 0;j<i;j++) {
				var e=Gp99(pa[i],pa[j]);
				var v=1L;
				if(e.Item1==0){
					if(e.Item3==0){v=(int)e.Item2;}
					else{v=Gcd((int)e.Item2,(int)e.Item3);}
				}
				else if(e.Item2==0){
					if(e.Item3==0){v=(int)e.Item1;}
					else{v=Gcd((int)e.Item1,(int)e.Item3);}
				}
				else{
					v=Gcd((int)e.Item1,(int)e.Item2);
					if(e.Item3!=0){v=Gcd(v,(int)e.Item3);}
				}
				var t=(e.Item1/v)+" "+(e.Item2/v)+" "+(e.Item3/v);
				if(hs.ContainsKey(t)){hs[t]++;}
				else{hs.Add(t,1);}
				ans=Max(ans,hs[t]);
			}
		}
		Console.WriteLine((int)Sqrt(ans<<1)+1);
	}
	static long Gcd(long a,long b){
		long c=Max(a,b)%(b=Min(a,b));
		while(c!=0){
			a=b%c;
			b=c;
			c=a;
		}
		return b;
	}
}

public struct Pair{
	public double x,y;
	public Pair(double x,double y){this.x=x;this.y=y;}
	public Pair(double[] da){x=da[0];y=da[1];}
	public Pair(Pair p){x=p.x;y=p.y;}
	public override string ToString()=>x.ToString()+" "+y.ToString();
	public static Pair operator+(Pair a,Pair b){a.x+=b.x;a.y+=b.y;return a;}
	public static Pair operator-(Pair a,Pair b){a.x-=b.x;a.y-=b.y;return a;}
	public static Pair operator*(Pair a,double n){a.x*=n;a.y*=n;return a;}
	public static Pair operator/(Pair a,double n){a.x/=n;a.y/=n;return a;}
}
static class Exg{
	static public double Gp0(Pair a,Pair b){return Sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
	static public Tuple<bool,Pair> Gp1(Pair p1,Pair p2,Pair p3,Pair p4){
		double t1=(p4.y-p3.y)*(p4.x-p1.x)-(p4.x-p3.x)*(p4.y-p1.y);
		double t2=(p2.x-p1.x)*(p4.y-p1.y)-(p2.y-p1.y)*(p4.x-p1.x);
		double t3=(p2.x-p1.x)*(p4.y-p3.y)-(p2.y-p1.y)*(p4.x-p3.x);
		if(t3==0){
			if(Abs(Atan2(p2.y-p1.y,p2.x-p1.x))!=Abs(Atan2(p3.y-p1.y,p3.x-p1.x))){return Tuple.Create(p1.x==p3.x&&p1.y==p3.y?true:false,p1);}
			var a=new Tuple<Pair,int>[]{Tuple.Create(p1,1),Tuple.Create(p2,2),Tuple.Create(p3,3),Tuple.Create(p4,4)};
			Array.Sort(a,(d,e)=>{var c=d.Item1.x.CompareTo(e.Item1.y);return c==0?e.Item1.y.CompareTo(d.Item1.y):c;});
			return Tuple.Create((Abs(a[0].Item2-a[1].Item2)!=1||Abs(a[2].Item2-a[3].Item2)!=1)||(a[1].Item1.x==a[2].Item1.x&&a[1].Item1.y==a[2].Item1.y)?true:false,a[1].Item1);
		}
		double t4=t1/t3,t5=t2/t3;
		if(t4<0||t4>1||t5<0||t5>1){return Tuple.Create(false,new Pair(0,0));}
		else{return Tuple.Create(true,new Pair(p1.x+t4*(p2.x-p1.x),p1.y+t4*(p2.y-p1.y)));}
	}
	static public double Gp2(Pair p1,Pair p2,Pair p0){return Abs((p2.y-p1.y)*p0.x-(p2.x-p1.x)*p0.y+p2.x*p1.y-p1.x*p2.y)/Sqrt((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));}
	static public double Gp3(Pair p1,Pair p2,Pair p0){return (p1.x-p2.x)*(p0.y-p1.y)+(p1.y-p2.y)*(p1.x-p0.x);}
	static public double Gp4(Pair a,Pair b,Pair c){
		double a1=a.x-b.x,a2=a.y-b.y,c1=c.x-b.x,c2=c.y-b.y;
		return Acos((a1*c1+a2*c2)/Sqrt((a1*a1+a2*a2)*(c1*c1+c2*c2)))*180/PI;
	}
	static public Tuple<bool,Pair> Gp5(Pair p1,Pair p2,Pair p0){
		double rx=p0.x,ry=p0.y;
		if(p1.x==p2.x){rx=p1.x;}
		else if(p1.y==p2.y){ry=p1.y;}
		else{
			double m1=(p2.y-p1.y)/(p2.x-p1.x),b1=p1.y-(m1*p1.x),m2=-1.0/m1,b2=p0.y-(m2*p0.x);
			rx=(b2-b1)/(m1-m2);
			ry=(b2*m1-b1*m2)/(m1-m2);
		}
		return Tuple.Create(((p1.x>=rx&&p2.x<=rx)||(p2.x>=rx&&p1.x<=rx))&&((p1.y>=ry&&p2.y<=ry)||(p2.y>=ry&&p1.y<=ry)),new Pair(rx,ry));
	}
	static public Pair Gp6(Pair a,Pair b,Pair c,int n){
		double l1=Sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
		double l2=Sqrt((c.x-b.x)*(c.x-b.x)+(c.y-b.y)*(c.y-b.y));
		double ex=(a.x+(b.x+(c.x-b.x)*(l1/l2)))/2,ey=(a.y+(b.y+(c.y-b.y)*(l1/l2)))/2;
		ex+=(ex-b.x)*n;ey+=(ey-b.y)*n;
		return new Pair(ex,ey);
	}
	static public Pair Gp7(Pair a,double k,double p){return new Pair(a.x+k*Cos(p),a.y+k*Sin(p));}
	static public bool Gp8(Pair a,Pair b,Pair c){return (c.x-a.x)*(b.y-a.y)==(b.x-a.x)*(c.y-a.y);}
	static public Pair Gp9(Pair a,Pair b,Pair c){
		double d=a.x*a.x+a.y*a.y,e=b.x*b.x+b.y*b.y,f=c.x*c.x+c.y*c.y,g=2*(a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y));
		return new Pair((d*(b.y-c.y)+e*(c.y-a.y)+f*(a.y-b.y))/g,(d*(c.x-b.x)+e*(a.x-c.x)+f*(b.x-a.x))/g);
	}
	static public Pair[] Gp10(Pair p0,double r,Pair p1,Pair p2){
		double a=p2.y-p1.y,b=p1.x-p2.x;
		double d=p0.x*-a+p0.y*-b+a*p1.x+b*p1.y;
		double g=a*a+b*b;
		double k=g*r*r-d*d;
		if(k<0){return new Pair[]{};}
		if(k==0){return new Pair[]{new Pair((a*d)/g+p0.x,(b*d)/g+p0.y)};}
		k=Sqrt(k);
		return new Pair[]{new Pair((a*d-b*k)/g+p0.x,(b*d+a*k)/g+p0.y),new Pair((a*d+b*k)/g+p0.x,(b*d-a*k)/g+p0.y)};
	}
	static public Pair[] Gp11(Pair p1,double r1,Pair p2,double r2){
		p2-=p1;
		double a=(p2.x*p2.x+p2.y*p2.y+r1*r1-r2*r2)/2;
		double g=p2.x*p2.x+p2.y*p2.y;
		double k=g*r1*r1-a*a;
		if(k<0){return new Pair[]{};}
		if(k==0){return new Pair[]{new Pair((p2.x*a)/g,(p2.y*a)/g)+p1};}
		k=Sqrt(k);
		return new Pair[]{new Pair((p2.x*a+p2.y*k)/g,(p2.y*a-p2.x*k)/g)+p1,new Pair((p2.x*a-p2.y*k)/g,(p2.y*a+p2.x*k)/g)+p1};
	}
	static Tuple<double,double> Gp12(Pair[] pa){
		int n=pa.Length;
		double sumx=0,sumy=0,sumxy=0,sumx2=0;
		for(int i = 0;i<n;i++) {
			sumxy+=pa[i].x*pa[i].y;
			sumx+=pa[i].x;
			sumy+=pa[i].y;
			sumx2+=pa[i].x*pa[i].x;
		}
		return Tuple.Create((n*sumxy-sumx*sumy)/(n*sumx2-sumx*sumx),(sumx2*sumy-sumxy*sumx)/(n*sumx2-sumx*sumx));
	}
	static public Pair[] Gp13(Pair a,Pair p1,double r){
		a-=p1;
		double g=a.x*a.x+a.y*a.y,k=Sqrt(g-r*r);
		return new Pair[]{new Pair(r*(a.x*r+a.y*k)/g,r*(a.y*r-a.x*k)/g)+p1,new Pair(r*(a.x*r-a.y*k)/g,r*(a.y*r+a.x*k)/g)+p1};
	}
	static public Tuple<double,double,double> Gp99(Pair a,Pair b){
		double d=b.y-a.y,e=a.x-b.x;
		return Tuple.Create(-d,-e,d*a.x+e*a.y);
	}
	static public Tuple<Pair,double>[] Psort(Pair[] pa,Pair p){
		var arr=new Tuple<Pair,double>[pa.Length];
		for(int i = 0;i<pa.Length;i++) {arr[i]=Tuple.Create(pa[i],Atan2(pa[i].y-p.y,pa[i].x-p.x)*180/PI+180);}
		Array.Sort(arr,(u,v)=>u.Item2.CompareTo(v.Item2));
		return arr;
	}
	static public Tuple<Pair,double>[] Psort2(Pair[] pa,Pair p){
		int n=pa.Length;
		var arr=new Tuple<Pair,double>[n];
		for(int i = 0;i<n;i++) {arr[i]=Tuple.Create(pa[i],Atan2(pa[i].y-p.y,pa[i].x-p.x)*180/PI+180);}
		Array.Sort(arr,(u,v)=>u.Item2.CompareTo(v.Item2));
		Array.Resize(ref arr,n<<1);
		for(int i = 0;i<n;i++) {arr[i+n]=Tuple.Create(arr[i].Item1,arr[i].Item2+360);}
		return arr;
	}
}
public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
	public object[] Oa{get{return Console.ReadLine().Split();}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
	public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}
	public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
	public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}
	public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);}
	public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}
	public double[] Da3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),double.Parse);}
	public double[] Da3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),double.Parse);}
	public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
	public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
	public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
	public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}
0