Hatena::Grouptopcoder

kuuso1の日記

2016-09-24

September Lunchtime 2016 Chef and Triangles

| 05:06 | September Lunchtime 2016 Chef and Triangles - kuuso1の日記 を含むブックマーク はてなブックマーク - September Lunchtime 2016 Chef and Triangles - kuuso1の日記

https://www.codechef.com/LTIME40/problems/LTM40CD

  • 正の整数 R が与えられる。
  • 与えられたR が内接円の半径となる,3辺の長さがすべて整数の三角形をすべて列挙せよ

(制約)1 ≤ R ≤ 100

・内接円に関する記憶をさかのぼると,各辺に直交するので面積と関係したはず.

・辺長が満たすべき式が結構きれいになった.

f:id:kuuso1:20160925045344p:image

・探索範囲は a については a = 1 の時に一番平たい鈍角三角形になって,そこからaを増やすに従って三角形が立ち上がってくる.

 なので,一番小さいaの範囲は正三角形になるまでの√3 R くらいで抑えられる.

・b についてはよくわからなかったので,ざっくり上界を 4R^2 にして投げたら通ってしまった...

・あとは (a,b,c) から三角形の辺長を確定させて,三角不等式を満たすかどうかをベリファイした.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		List<long[]> L = new List<long[]>();
		for(long a=1;a<=2*R;a++){
			for(long b=a;b<=4*R*R;b++){
				if((a*b-R*R) != 0 && (R*R*a+R*R*b)%(a*b-R*R) == 0){
					long c = (R*R*a+R*R*b)/(a*b-R*R);
					if(isValid(a,b,c)){
						var s = new long[] {a+b,b+c,c+a};
						Array.Sort(s);
						L.Add(s);
					}
				}
			}
		}
		
		L.Sort( (p,q) => p[0]>q[0]?1:p[0]<q[0]?-1:p[1]>q[1]?1:p[1]<q[1]?-1:p[2]>q[2]?1:p[2]<q[2]?-1:0);
		
		Console.WriteLine(L.Count);
		foreach(var s in L){
			Console.WriteLine(String.Join(" ",s));
		}
		
		
	}
	
	bool isValid(long a,long b,long c){
		if(a<=0 || b<=0 || c<=0)return false;
		if(a+b+b+c<c+a)return false;
		if(b+c+c+a<a+b)return false;
		if(c+a+a+b<b+c)return false;
		return (a<=b && b<=c);
	}
	
	long R;
	public Sol(){
		R = rl();
	}

	static long rl(){return long.Parse(Console.ReadLine());}
}

・本番ほとんど通している人がいなくてまさかの10位で申し訳なさがあったので,嘘解法を供養するということで一応上界をちゃんと抑えておきました.

(実験したからそこまで嘘解法でもなかったのだけど)