Andrew Stankevich’s Contest #6解题报告 » ZOJ2600

ZOJ2600
ZOJ2600.java


import java.math.*;
import java.util.*;

class BMath {
	static int cnt1, cnt2;
	public static MathContext mc = null;
	public static BigDecimal eps = null;
	public static BigDecimal two = null;
	public static BigDecimal sqrt3 = null;
	public static BigDecimal pi = null;

	static {
		mc = new MathContext(128);
		eps = BigDecimal.ONE.scaleByPowerOfTen(-128);
		two = BigDecimal.valueOf(2);
		// sqrt3 = sqrt(BigDecimal.valueOf(3));
		// pi = asin(BigDecimal.valueOf(0.5)).multiply(BigDecimal.valueOf(6));
sqrt3 = new BigDecimal("1.73205080756887729352744634150587236694280525381038062805580697945193301690880003708114618675724857567562614141540670302996994510");
pi = new BigDecimal("3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384444");
		// System.err.printf("sqrt3 = new BigDecimal(\"%.128f\");\n", sqrt3);
		// System.err.printf("pi = new BigDecimal(\"%.128f\");\n", pi);
	}

	/*
	// val > 0
	public static BigInteger sqrt(BigInteger val) {
		int len = val.bitLength();
		BigInteger left = BigInteger.ONE.shiftLeft((len - 1) / 2);
		BigInteger right = BigInteger.ONE.shiftLeft(len / 2 + 1);
		while (left.compareTo(right) < 0) {
			BigInteger mid = left.add(right).shiftRight(1);
			if (mid.multiply(mid).compareTo(val) <= 0) {
				left = mid.add(BigInteger.ONE);
			} else {
				right = mid;
			}
		}
		return right.subtract(BigInteger.ONE);
	}

	public static BigDecimal sqrt(BigDecimal val) {
		BigInteger unscaledVal = val.scaleByPowerOfTen(2 * mc.getPrecision()).toBigInteger();
		return new BigDecimal(sqrt(unscaledVal)).scaleByPowerOfTen(-mc.getPrecision());
	}
	*/
	public static BigDecimal sqrt(BigDecimal val) {
		BigDecimal a = BigDecimal.ONE;
		BigDecimal b = a.add(val.divide(a, mc)).divide(two, mc);
		while (b.subtract(a).abs().compareTo(eps) > 0) {
			a = b;
			b = a.add(val.divide(a, mc)).divide(two, mc);
			// ++cnt1;
		}
		return b;
	}

	// arcsin x =∑(n=1~∞) [(2n)!]x^(2n+1)/[4^n*(n!)^2*(2n+1)]
	// arctan x =∑(n=1~∞) [(-1)^n]x^(2n+1)/(2n+1)
	public static BigDecimal asin(BigDecimal val) {
		BigDecimal tmp = val;
		BigDecimal ret = tmp;
		val = val.multiply(val, mc);
		for (int n = 1; tmp.compareTo(eps) > 0; ++n) {
			tmp = tmp.multiply(val, mc).multiply(
					BigDecimal.valueOf(2 * n - 1).divide(BigDecimal.valueOf(2 * n), mc), mc);
			ret = ret.add(tmp.divide(BigDecimal.valueOf(2 * n + 1), mc), mc);
			// ++cnt2;
		}
		return ret;
	}
}

public class Main {
	static BigDecimal c = BMath.sqrt3.divide(B(4));

	static int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}

	static BigDecimal B(double val) {
		return BigDecimal.valueOf(val);
	}

	static BigDecimal[][] ansCache = new BigDecimal[52][52];

	static {
ansCache[8][7] = new BigDecimal("0.92233554316552589847060760268962309292371943029544370527259157008422729068059159183263216797838756932366649829932993541092967200");
ansCache[9][8] = new BigDecimal("0.94127830504682436799041953931602782548143073641582752461948389511704899230990959603389415064331408971614102636291662205083760258");
ansCache[10][9] = new BigDecimal("0.95372808562138859768168392892974945544125067576812487236496792758772801082654488672606336320585997227669745972639954576911765997");
ansCache[11][10] = new BigDecimal("0.96249669800100245905174082069563528617512121403415186716068851326051917130259757939444837457238484922101006947815252415791091508");
ansCache[12][11] = new BigDecimal("0.96894588202437734205981909012098912870124929653861706064070768583069911905591471540297225798846579868605886435137595078501150977");
ansCache[13][12] = new BigDecimal("0.97384254544993059533184710747221719980099085594193136038814986241848841100102228678315420786506005244885862897480271781134566823");
ansCache[14][13] = new BigDecimal("0.97765464011952470309216102253186653056229234343772536171483678270348435956599586256815486303625197750461483780389910127584794754");
ansCache[15][13] = new BigDecimal("0.90817741307717222102128707827053743693572222825587920271161488350013768737071308793212300850845259922419230848249516941487905673");
ansCache[15][14] = new BigDecimal("0.98068368715083960879047100469703885492568928680653561028912968410077795635082101676833520200159774811716122589061907869740614694");
ansCache[16][15] = new BigDecimal("0.98313212004258547666249782368838115624792391886175456520281104440717873295923041418839097036838262738787785363077627902214377610");
ansCache[17][15] = new BigDecimal("0.93290802997167594664795470790773939444671022686305822122998666169412331966309584615004956632875506771554988018252894755687016588");
ansCache[17][16] = new BigDecimal("0.98514038014059018407166399740928326319044977855674311170169741636980945183620443076558587587047747782362860485562876763989062171");
ansCache[18][17] = new BigDecimal("0.98680857997083633884553866850626967133635373969430069678718260137592750061339640642712740176491505462094799503701637571857527851");
ansCache[19][17] = new BigDecimal("0.94808698342614844474005700905287616179393371342835259891449674359532645611193467147674798257918394715360267839696315133006161711");
ansCache[19][18] = new BigDecimal("0.98820974245996755925565338180482750695240423806912293660370778870226458243807369189932850518926356992962604937834195176947599087");
ansCache[20][19] = new BigDecimal("0.98939819632398456007983019332409260224019978000239272886065798545222591285144831398920523529618313739441272113441254898152345258");
ansCache[21][19] = new BigDecimal("0.95846805154558881007814045979625590251748256737543704449104404409087477542207520353239572979428846189467159258531411815478251348");
ansCache[21][20] = new BigDecimal("0.99041506712928726004060883835323135138738718449773874366993306231586511422296071840154325598248514761942207522525090944625042532");
ansCache[22][21] = new BigDecimal("0.99129196512372843168441887044853353056173934818519603055423602711771448637765659969281520115639258791414760017625105519686786391");
ansCache[23][20] = new BigDecimal("0.91347391047030196679680808288425497454999031054407788547055648532625294055639959095396852914479187503861908765713419442607364111");
ansCache[23][21] = new BigDecimal("0.96595401053407484588949512866367598612782925774961718740261695644868900068428631586996643258278865086044514085114635506097089778");
ansCache[23][22] = new BigDecimal("0.99205351969897990225010380302933030697753275404497614766005369892618269871421443851727534553254845720400982832523628048258436099");
ansCache[24][23] = new BigDecimal("0.99271915687705906911344655866823981899774849746693382149125056056097590742691486164725533150633648506235942584628789496544344235");
ansCache[25][22] = new BigDecimal("0.92967181048880780219495938714132574663000433171495142471682260090665503047060294601469531429347248089536043616227009998042352589");
ansCache[25][23] = new BigDecimal("0.97155402816666888108519885390567224047481016978055441424573916680460413213711586818118959158199135299851218022568087674722126596");
ansCache[25][24] = new BigDecimal("0.99330436859450020002777213070216442886366042450973620879274396889018379532772714270287097810143429150964794131567698055666907816");
ansCache[26][23] = new BigDecimal("0.93590388793393062422338970497742249582669191045659749122912165421978847575955052146177858199699689352460435091332116253418512277");
ansCache[26][25] = new BigDecimal("0.99382163386315056108606467073280974269810375898853555556278351624574081526464479110060729941758547844411802874006595972697126964");
ansCache[27][25] = new BigDecimal("0.97586240811163059446988396150739919435886814339861482890760642496141195328506947626168852109089065965225243421563105230896465233");
ansCache[27][26] = new BigDecimal("0.99428109712269407485331109319896204013680868689245603222079002089965686698082530554326829517830818070914577468800479981270322110");
ansCache[28][25] = new BigDecimal("0.94596329067038241045854326337839683514599843061069870057150038698544877880108725959655993213946122292575508195600794286254949160");
ansCache[28][27] = new BigDecimal("0.99469107445973342137178570507236175350738957118612520380394237905560102604080813411822753329821583439659714598331420419404553118");
ansCache[29][26] = new BigDecimal("0.95008193933798608956389620400877450156316931947272786014123786674948245077582535289037645958968882699767181122858861873078232770");
ansCache[29][27] = new BigDecimal("0.97925260443590053745803444900065882671923242843118940730047435473709440482888399747411591150872513648515740716178531349309453366");
ansCache[29][28] = new BigDecimal("0.99505843597853776168557105024429287858361478293774726466492159846030140199183319868873699715108509988424041696699525075684706351");
ansCache[30][29] = new BigDecimal("0.99538889785245138001799191989812255328172962096498201715430092810793011465099560563569007988599352171751416014528862976923489504");
ansCache[31][27] = new BigDecimal("0.91586957130708701540134243907563850039606737052506280628287726057079439867871607617342625471091405786562611122828229166552658615");
ansCache[31][28] = new BigDecimal("0.95697525212841296245474272027799447605082589830241577749566348817995621617222001467114415633580469108535503379069610852717877514");
ansCache[31][29] = new BigDecimal("0.98197055687957763394356197013196461075175325863003169538766973835496684962359534760348583501042053206906002075808250898744214072");
ansCache[31][30] = new BigDecimal("0.99568724768646751202884739805401768226749527858416174695494625600387109578981855419178305295799379521984971787041354953935778201");
ansCache[32][29] = new BigDecimal("0.95988221484407848509707746591103009135311503494031995104948156463418978079313891922538829901055917281918868905229158568113930249");
ansCache[32][31] = new BigDecimal("0.99595752007354200049097391166431241941796686537617242202299648517720338254098099913426323760784061674030501283039738389584762048");
ansCache[33][29] = new BigDecimal("0.92795344945243444893287410581383235872431867741427316372502101274092841059917921896299201118280238955533106894998627306479250771");
ansCache[33][31] = new BigDecimal("0.98418425462511114573954588376134993219013313802967212204656269662949452371825730151580957401926314214308630443825708348908270232");
ansCache[33][32] = new BigDecimal("0.99620313455850338602019869819034913013372971755198635866612075859265060880899409374842708095331722591594524876811326405781415385");
ansCache[34][31] = new BigDecimal("0.96485794313686502862646248942854423683521490665943416282079791943476048865636974772694209559200687706651517199213059043174665328");
ansCache[34][33] = new BigDecimal("0.99642700494891534951990863443079022294470905693755402960267834783246735797451111077303717867584145865685883685260147970255517058");
ansCache[35][31] = new BigDecimal("0.93732033906353834305395482014238043276014430294983697890064344448155423701089435746885520919219531961171215580461865439142209136");
ansCache[35][32] = new BigDecimal("0.96699855784202685489191510397575809406106168924624222496976591237861308391772984662606645454545311498155856929223030885379955479");
ansCache[35][33] = new BigDecimal("0.98601190485955983178754067852725527427482030114798139310334212666386228803945722302498931350200203631964677624809629836753615321");
ansCache[35][34] = new BigDecimal("0.99663162658646760662582461284903308615846266478820801763272071484240283354853581667289782234797026168347576603224024584149726458");
ansCache[36][35] = new BigDecimal("0.99681914652109268698488028904384674961547291370825280124513712589702747275564920625871800683197357902539818392456570134421407368");
ansCache[37][33] = new BigDecimal("0.94484935774857428432332902006765077558692709730537761418989737145975557676394887742652103121134803878773774713470761910691811216");
ansCache[37][34] = new BigDecimal("0.97072301930711858340998177219025887552583862082965301021974628218547679708373016421573690470947858667766532438539139168300629278");
ansCache[37][35] = new BigDecimal("0.98753878240781872630778894158375460422450145834340989522071633992896955544113293503741127524680121265239077685276230883041254170");
ansCache[37][36] = new BigDecimal("0.99699142031574080728493863362449258882583694499596790926969234807911684491872751636153994314265526130733449932749021801058214036");
ansCache[38][33] = new BigDecimal("0.91144842272829570576591548903796479425762634276252423379326836546047913105596859368899374496683801587136748808067239774100432568");
ansCache[38][35] = new BigDecimal("0.97234962934319630392014485675354980397074620153467045344609168696665789431035347287924836539948876059109078023470865524959697208");
ansCache[38][37] = new BigDecimal("0.99715005831855350441102272502713650859721459716464969960747975721203613425276745957626982210271521969571298541457094127638762785");
ansCache[39][34] = new BigDecimal("0.91724342751447752226746504222596008657868355739893581517382032367969683800228034543705940491605041452608394049878116122634432931");
ansCache[39][35] = new BigDecimal("0.95103460528557594101804731813531132001805438502771071536961397063556873506123461747089884418352469180366178150674936024376267910");
ansCache[39][37] = new BigDecimal("0.98882772826178404759356403383065800571055550818277406954336448319022532899113207332497629203573103107977389752637865661046795525");
ansCache[39][38] = new BigDecimal("0.99729646357884038421722960211317911370647478753559607145325904211558496558179618853583506493219729749410562396784022132522510160");
ansCache[40][37] = new BigDecimal("0.97521626214586968089470469593550120750876009134780123248210869259888505207673081457381400350966056206064535436998452020808299620");
ansCache[40][39] = new BigDecimal("0.99743186308958852761338907209412121228682829240703203603002068460589951966373940936804574389843798209360519024336119060375277788");
ansCache[41][36] = new BigDecimal("0.92688762425167379626371718455392558444021382022383413805061063108018167858045782430240557136859963041308133975579667357360400241");
ansCache[41][37] = new BigDecimal("0.95619743809304961918899778954676597287582589354635367263247618294896483604353874616470784685005251636941328411100442439684208013");
ansCache[41][38] = new BigDecimal("0.97648332420608936508986927532955602361635130360121503227961920138013276484024789282038803621383637019645504749098390900645146796");
ansCache[41][39] = new BigDecimal("0.98992591511858166539586368852728323492532451477452654837262741839874130537929035091354684868028765879437176116682926816997879154");
ansCache[41][40] = new BigDecimal("0.99755733366704198292947513112174179468253740133208773980584583897459592243749197856451305079882701193036334585164544066474067036");
ansCache[42][37] = new BigDecimal("0.93099711023192702391664676567701332282574939851616015879604517517836356796109424835685117037295268320684407176916227370928383765");
ansCache[42][41] = new BigDecimal("0.99767382349505372232010848964993229242514925447567602923126359095055656639931452670412742776021027473447540442668737955403399900");
ansCache[43][38] = new BigDecimal("0.93473253768019141614189078980779437560374729228056633446681279838938662687069123816788768302020157521774168102956654329171977311");
ansCache[43][39] = new BigDecimal("0.96056159402788670352142907673263810098126882360909188616183225374470838307814048672934588844646870607394458101309357540465574062");
ansCache[43][40] = new BigDecimal("0.97873973680319539806776023498025708439043865314838838803673371086109764252334291326312442724816945106287670952770974856053278826");
ansCache[43][41] = new BigDecimal("0.99086933357743380364323810434598712574073832774698814911857682988515880789928400079679731260387199851324663725308186855157064929");
ansCache[43][42] = new BigDecimal("0.99778217014536808205915289313789364710582283283917548418444807700484144222873995639424438886422569620224989505667728547262846890");
ansCache[44][39] = new BigDecimal("0.93814587946658134600517330971394716535201740819207723065892524496435125955245367776995782859110721614543307593770773284057340626");
ansCache[44][41] = new BigDecimal("0.97974696817713237894668627064412208519947485259921763279524298661786787451188685484626500988160827054911275025534078618492396139");
ansCache[44][43] = new BigDecimal("0.99788311571802421200771721309207022637011880854918110964658874300372393135868890132736899616972974396515197267643758067622539328");
ansCache[45][41] = new BigDecimal("0.96428949053112138220403957119132800773993105489070993777600783640290603051551534443855197209256780601357485170155491634660534402");
ansCache[45][43] = new BigDecimal("0.99168584115112248975414102062880240089887970638588358196696113187452676021569878418830778382720177260372334716598535239982081166");
ansCache[45][44] = new BigDecimal("0.99797731961646462640896338968328775279686916201550757120941884339822811367172025575500535438874821593232709389426316602898278305");
ansCache[46][41] = new BigDecimal("0.94416336861333190009584191890752739674962254227717654086347331196154514705438516058865933284685113978433579147514730070145153243");
ansCache[46][43] = new BigDecimal("0.98155638834418304313934744968659940460187139800760112248867695016328791468945256917194663218133819310491067120408729473920562397");
ansCache[46][45] = new BigDecimal("0.99806536937068606121751754535068434174636766621149278974558786415250136351514576000413246253390406222884973259907561014853530954");
ansCache[47][41] = new BigDecimal("0.91813520056760106411162493662217143050743012791401325976176112516187469109006609327605965036172083735035100538225475475096961170");
ansCache[47][42] = new BigDecimal("0.94682897364939550270451438264632150974919487264551767453738351325023326456463983303994353382080303601384647175803716105977569538");
ansCache[47][43] = new BigDecimal("0.96750254180314545109111193845024835382173845957097376796046956603242205857948279549832934243805115816724405922339559342308511569");
ansCache[47][44] = new BigDecimal("0.98237082721659976642323697282022568510902410448784495609839097421501275181621794713340961454701450716914915938604441467098426306");
ansCache[47][45] = new BigDecimal("0.99239727970372431106949846592256149143269632841997415329331650114593019220478703665398648449892228310487023226131341886189801568");
ansCache[47][46] = new BigDecimal("0.99814778984219796018274066943818569270460524880597245528481686871831793937937565137612597195104330565640222278271383596332010459");
ansCache[48][43] = new BigDecimal("0.94929867619871252168719363989627499204070431086163214324513782747707780434343548463393706199661987370316327256484495125057172139");
ansCache[48][47] = new BigDecimal("0.99822505108165646311549316441143955595988096644048050578307340906018442631506286417787286175721137303772680612991079498333845705");
ansCache[49][43] = new BigDecimal("0.92616185578835745872455870417724818489009526551448158289049742229734191669498810632506521352002411236708320608310059333531286785");
ansCache[49][44] = new BigDecimal("0.95159259692917888422621020752796367163743575584701138139332997040209201688054893440078562873763410367142051607183388390579930459");
ansCache[49][45] = new BigDecimal("0.97029356233915643908839812658900478083513562624854004161410854879658412959674735952292103290045025891470171748822835758716681198");
ansCache[49][46] = new BigDecimal("0.98384482823457965976785111565214910904195025598196649766510602967898010269225294380116861282765848763524936379738499372083674953");
ansCache[49][47] = new BigDecimal("0.99302097429812308853309227661470918095559752566409066682132797128728837640070873826995694885845929374235839536720919461529899948");
ansCache[49][48] = new BigDecimal("0.99829757506005170431965878890943013010983964036822214874519136792670733846626319640153022637097824617327950487993378876080148010");
ansCache[50][47] = new BigDecimal("0.98451302979698180310018085619028469741866686583424668241728873534676912670242017381769233473449336186969315063959618457745130747");
ansCache[50][49] = new BigDecimal("0.99836574145438680017322767197831715163900489048344625303298811817264572556867272032668017976955716669705966843810237764950026073");
	}

	static BigDecimal getAns(int h, int r) {
		int g = gcd(h, r);
		h /= g;
		r /= g;
		if (ansCache[h][r] != null) {
			return ansCache[h][r];
		}

		BigDecimal bc = BMath.sqrt(B(r * r).subtract(B(3 * h * h).divide(B(4))));
		BigDecimal sina = bc.divide(B(r), BMath.mc);
		BigDecimal a = BMath.asin(sina);

		BigDecimal sub = null;
		sub = B(h).multiply(c).multiply(B(h).subtract(bc.multiply(B(2))), BMath.mc);
		sub = sub.subtract(B(r * r).multiply(BMath.pi.divide(B(6), BMath.mc).subtract(a)));
		BigDecimal tri = B(h * h).multiply(c);
		ansCache[h][r] = BigDecimal.ONE.subtract(sub.divide(tri, BMath.mc));

		System.err.printf("ansCache[%d][%d] = new BigDecimal(\"%.128f\");\n", h, r, ansCache[h][r]);
		return ansCache[h][r];
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (true) {
			int h = in.nextInt();
			int r = in.nextInt();
			BigDecimal ans = null;
			if (h == 0 && r == 0) {
				break;
			} else if (r >= h) {
				ans = BigDecimal.ONE;
			} else if (4 * r * r <= 3 * h * h) {
				BigDecimal cir = B(r * r).multiply(BMath.pi);
				BigDecimal hex = B(h * h).multiply(c.multiply(B(6)));
				ans = cir.divide(hex, BMath.mc);
			} else {
				ans = getAns(h, r);
			}
			System.out.printf("%.110f\n", ans);
		}
		// System.err.println(BMath.cnt1 + " " + BMath.cnt2);
		// 1555 16777
	}
}

// run all case -- real	0m1.673s => TLE

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name
//2175716 	2010-04-24 21:48:34 	Accepted 	2600 	Java 	190 	2318 	watashi@Zodiac
Leave a Reply