結果

問題 No.245 貫け！
コンテスト
ユーザー kuuso1
提出日時 2015-07-18 00:00:22
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 654 ms / 5,000 ms
コード長 4,534 bytes
コンパイル時間 877 ms
コンパイル使用メモリ 116,528 KB
実行使用メモリ 19,968 KB
最終ジャッジ日時 2024-07-08 09:47:42
合計ジャッジ時間 7,496 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
using System.Collections.Generic;
 
class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		int cMax=0;
		int cnt=0;
		for(int i=0;i<N;i++){
			for(int j=i;j<N;j++){
				
				var E=longEdge(A[i],B[i]);
				cnt=0;
				for(int k=0;k<N;k++){
					if(Intersect(E[0],E[1],A[k],B[k]))cnt++;
				}
				cMax=Math.Max(cMax,cnt);
		
				E=longEdge(A[i],A[j]);
				cnt=0;
				for(int k=0;k<N;k++){
					if(Intersect(E[0],E[1],A[k],B[k]))cnt++;
				}
				cMax=Math.Max(cMax,cnt);
				
				E=longEdge(A[i],B[j]);
				cnt=0;
				for(int k=0;k<N;k++){
					if(Intersect(E[0],E[1],A[k],B[k]))cnt++;
				}
				cMax=Math.Max(cMax,cnt);
				
				E=longEdge(B[i],A[j]);
				cnt=0;
				for(int k=0;k<N;k++){
					if(Intersect(E[0],E[1],A[k],B[k]))cnt++;
				}
				cMax=Math.Max(cMax,cnt);
		
				E=longEdge(B[i],B[j]);
				cnt=0;
				for(int k=0;k<N;k++){
					if(Intersect(E[0],E[1],A[k],B[k]))cnt++;
				}
				cMax=Math.Max(cMax,cnt);
		
				E=longEdge(A[j],B[j]);
				cnt=0;
				for(int k=0;k<N;k++){
					if(Intersect(E[0],E[1],A[k],B[k]))cnt++;
				}
				cMax=Math.Max(cMax,cnt);
			}
		}
		
		Console.WriteLine(cMax);
		
		
	}
	int N;
	Pair[] A,B;
	public Sol(){
		N=ri();
		A=new Pair[N];
		B=new Pair[N];
		for(int i=0;i<N;i++){
			var d=ria();
			A[i]=new Pair(d[0],d[1]);
			B[i]=new Pair(d[2],d[3]);
		}
	}

	static bool Intersect(Pair a1,Pair a2,Pair b1,Pair b2){
		//do edges "this" and "other" intersect?
		
		if(Math.Min(a1.X,a2.X)>Math.Max(b1.X,b2.X))return false;
		if(Math.Max(a1.X,a2.X)<Math.Min(b1.X,b2.X))return false;
		if(Math.Min(a1.Y,a2.Y)>Math.Max(b1.Y,b2.Y))return false;
		if(Math.Max(a1.Y,a2.Y)<Math.Min(b1.Y,b2.Y))return false;
		
		int den=(b2-b1).Y*(a2-a1).X-(b2-b1).X*(a2-a1).Y;
		int num1=(b2-b1).X*(a1.Y-b1.Y)-(b2-b1).Y*(a1.X-b1.X);
		int num2=(a2-a1).X*(a1.Y-b1.Y)-(a2-a1).Y*(a1.X-b1.X);
		
		if(den==0){
			if(Math.Min(dist2(a1,a2,b1,b2),dist2(b1,b2,a1,a2))>0) return false;
			//on the same line - "not intersect" only if one of the vertices is common,
			//and the other doesn't belong to the line
			if(Pair.eqCo(a1,b1) && (a2-a1).L2()+(b2-b1).L2()==(b2-a2).L2())return false;
			if(Pair.eqCo(a1,b2) && (a2-a1).L2()+(b2-b1).L2()==(b1-a2).L2())return false;
			if(Pair.eqCo(a2,b1) && (a2-a1).L2()+(b2-b1).L2()==(b2-a1).L2())return false;
			if(Pair.eqCo(a2,b2) && (a2-a1).L2()+(b2-b1).L2()==(b1-a1).L2())return false;
			
			return true;
		}
		
		//common vertices
		if(Pair.eqCo(a1,b1)||Pair.eqCo(a1,b2)||Pair.eqCo(a2,b1)||Pair.eqCo(a2,b2))return false;

		double u1 = num1*1.0/den;
		double u2 = num2*1.0/den;
		if (u1<0 || u1>1 || u2<0 || u2>1)return false;
		return true;
	}
	

	struct Pair{
		public int X;
		public int Y;
		public Pair(int x,int y){
			X=x;Y=y;
		}
		public static Pair operator-(Pair p,Pair q){
			return new Pair(p.X-q.X,p.Y-q.Y);
		}
		public static Pair operator*(int r,Pair p){
			return new Pair(r*p.X,r*p.Y);
		}
		public static Pair operator+(Pair p,Pair q){
			return new Pair(p.X+q.X,p.Y+q.Y);
		}
		public static int det(Pair p,Pair q){
			return (p.X*q.Y-p.Y*q.X);
		}
		public static int dot(Pair p,Pair q){
			return (p.X*q.X+p.Y*q.Y);
		}
		public int L2(){
			return X*X+Y*Y;
		}
		public double L(){
			return Math.Sqrt(X*X+Y*Y);
		}
		public static bool eqCo(Pair p,Pair q){
			return p.X==q.X&&p.Y==q.Y;
		}
	}
	static double dist(Pair e1,Pair e2,Pair x){
		
		if(Pair.dot(e2-e1,x-e1)<=0){
			return (x-e1).L();
		}
		if(Pair.dot(e2-e1,x-e2)>=0){
			return (x-e2).L();
		}
		return Math.Abs(-(e2-e1).Y*x.X+(e2-e1).X*x.Y+e1.X*e2.Y-e1.Y*e2.X)/(e2-e1).L();
	}
    // ---------------------------------------------------
	static double dist2(Pair e1,Pair e2,Pair x1,Pair x2) {
		//distance from the closest of the endpoints of "other" to "this"
		return Math.Min(dist(e1,e2,x1), dist(e1,e2,x2));
	}
	
	Pair[] longEdge(Pair a,Pair b){
		return new Pair[]{
			b+100*(b-a),
			a+100*(a-b)
		};
	}



	



	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(){return Console.ReadLine().Split(' ');}
	static int[] ria(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>int.Parse(e));}
	static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));}
	static double[] rda(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>double.Parse(e));}
}
0