fork download
copy 
  1. #会津大学オンラインジャッジ問1089 Strawberry Cake合格堀江伸一
  2. def g(x1,y1,x2,y2)
  3. 	return x1*y2-y1*x2
  4. end
  5.  
  6. def lenCheck(x,y)
  7. 	dx=((x.negative?)?-1:1)*0.00000001
  8. 	dy=((y.negative?)?-1:1)*0.00000001
  9. 	add=0
  10. 	while x*x+y*y<1.0 && add<100
  11. 		x+=dx
  12. 		y+=dy
  13. 		add+=1
  14. 	end
  15.  
  16. 	return [x,y]
  17. end
  18.  
  19. def searchP(x1,y1,xs,ys,n)
  20. 	res=0
  21. 	n.times{|i|
  22. 		p1=i
  23. 		p2=(i+1)%n
  24. 		if 0<=g(xs[p1],ys[p1],-x1,-y1) && 0<=g(-x1,-y1,xs[p2],ys[p2]) then
  25. 			res=i
  26. 			break	
  27. 		end
  28. 	}
  29. 	return res
  30. end
  31.  
  32. def calcAllS(xs,ys,n)
  33. 	ans=0.0
  34. 	n.times{|i|
  35. 		x1=xs[i]
  36. 		y1=ys[i]
  37. 		x2=xs[(i+1)%n]
  38. 		y2=ys[(i+1)%n]
  39. 		ans+=g(x1,y1,x2,y2)
  40. 	}
  41. 	return (ans/2.0).abs
  42. end
  43.  
  44. def calcCross(n,p1,bx,by,xs,ys)
  45. 	p2=(p1+1)%n
  46. 	dx=xs[p2]-xs[p1]
  47. 	dy=ys[p2]-ys[p1]
  48. 	ax=xs[p1]
  49. 	ay=ys[p1]
  50. 	t=(by*ax-bx*ay)/(bx*dy-dx*by)
  51. 	rx=ax+t*dx
  52. 	ry=ay+t*dy
  53. 	return [rx,ry]
  54. end
  55.  
  56. def calcS(deep,n,p1,r1,r2,xs,ys,add)
  57. 	r3=(r1+r2)/2.0
  58. 	r1a=r3+add
  59.  
  60. 	bx=xs[p1]*(1.0-r1a)+xs[(p1+1)%n]*r1a
  61. 	by=ys[p1]*(1.0-r1a)+ys[(p1+1)%n]*r1a
  62. 	p2=searchP(bx,by,xs,ys,n)
  63.  
  64. 	ax=xs[p2]
  65. 	ay=ys[p2]
  66. 	dx=xs[(p2+1)%n]-xs[p2]
  67. 	dy=ys[(p2+1)%n]-ys[p2]
  68. 	xy=calcCross(n,p2,bx,by,xs,ys)
  69. 	areaXs=[]
  70. 	areaYs=[]
  71. 	p1a=[p1,p2].min
  72. 	p2a=[p1,p2].max
  73.  
  74. 	#n.times{|i|
  75. 	#	if p1a<i && i<=p2a then
  76. 	#		areaXs<<xs[i]
  77. 	#		areaYs<<ys[i]
  78. 	#	end
  79. 	#}
  80. 	s0=$memo[p2a]-$memo[(p1a+1)%n]
  81. 	s1=0.0
  82. 	if p1<p2 then
  83. 		#areaXs<<bx
  84. 		#areaYs<<by
  85. 		#areaXs<<xs[(p1a+1)%n]
  86. 		#areaYs<<ys[(p1a+1)%n]
  87. 		#areaXs<<xs[p2a]
  88. 		#areaYs<<ys[p2a]
  89. 		#areaXs<<xy[0]
  90. 		#areaYs<<xy[1]
  91. 		s1=g(bx,by,xs[(p1a+1)%n],ys[(p1a+1)%n])
  92. 		s1+=g(xs[p2a],ys[p2a],xy[0],xy[1])
  93. 		s1+=g(xy[0],xy[1],bx,by)
  94. 	else
  95. 		s1=g(xy[0],xy[1],xs[(p1a+1)%n],ys[(p1a+1)%n])
  96. 		s1+=g(xs[p2a],ys[p2a],bx,by)
  97. 		s1+=g(bx,by,xy[0],xy[1])
  98. 	end
  99. 	s1/=2.0
  100. 	#p [bx,by,xy[0],xy[1]]
  101. 	areaS=s1+s0
  102. 	#p ["s",areaS,areaS*2] if(deep==32)
  103. 	return areaS
  104. end
  105.  
  106. def searchB(deep,n,p1,r1,r2,xs,ys,allS)
  107. 	r3=(r1+r2)/2.0
  108. 	rx0=xs[p1]*(1.0-r3)+xs[(p1+1)%n]*r3
  109. 	ry0=ys[p1]*(1.0-r3)+ys[(p1+1)%n]*r3
  110. 	b1=false
  111. 	b1=true if rx0==xs[p1] && ry0==ys[p1]
  112. 	b1=true if rx0==xs[(p1+1)%n] && ry0==ys[(p1+1)%n]
  113. 	if 29<deep || b1==true then
  114. 		#rx0=xs[p1]*(1.0-r3)+xs[(p1+1)%n]*r3
  115. 		#ry0=ys[p1]*(1.0-r3)+ys[(p1+1)%n]*r3
  116. 		rxy0=lenCheck(rx0,ry0)
  117. 		rx=rxy0[0]
  118. 		ry=rxy0[1]
  119. 		s0=calcS(deep,n,p1,r3,r3,xs,ys,0.0)
  120. 		rd=(allS-s0*2).abs
  121. 		return [rd,rx,ry]
  122. 	else
  123. 		s1=calcS(deep,n,p1,r1,r2,xs,ys,0.0)
  124. 		d1=(s1*2-allS).abs
  125. 		s2=calcS(deep,n,p1,r1,r2,xs,ys,0.0000000001)
  126. 		d2=(s2*2-allS).abs
  127. 		if d1<d2 then
  128. 			return searchB(deep+1,n,p1,r1,r3,xs,ys,allS)
  129. 		else
  130. 			return searchB(deep+1,n,p1,r3,r2,xs,ys,allS)
  131. 		end
  132. 	end
  133. end
  134. def f(n)
  135. 	xs=[]
  136. 	ys=[]
  137. 	xs0=[]
  138. 	ys0=[]
  139.  
  140. 	n.times{
  141. 		x,y=gets.split(" ").map{|e| e.to_f}
  142. 		xs<<x
  143. 		ys<<y
  144. 		xs0<<x
  145. 		ys0<<y
  146. 	}
  147.  
  148. 	allS=calcAllS(xs,ys,n)
  149. 	xs0.size.times{|p1|
  150. 		n=xs.size
  151. 		bx=xs0[p1]
  152. 		by=ys0[p1]
  153. 		p2=searchP(bx,by,xs,ys,n)
  154. 		ax=xs[p2]
  155. 		ay=ys[p2]
  156. 		dx=xs[(p2+1)%n]-xs[p2]
  157. 		dy=ys[(p2+1)%n]-ys[p2]
  158. 		xy=calcCross(n,p2,bx,by,xs,ys)
  159. 		xs.insert(p2+1,xy[0])
  160. 		ys.insert(p2+1,xy[1])
  161. 	}
  162. 	n=xs.size
  163. 	$memo=[0.0]
  164. 	memos=0.0
  165. 	n.times{|p1|
  166. 		p2=(p1+1)%n
  167. 		memos+=g(xs[p1],ys[p1],xs[p2],ys[p2])/2.0
  168. 		$memo<<memos
  169. 	}
  170.  
  171. 	allAns=[]
  172. 	n.times{|i|
  173. 		p1=i
  174. 		p2=(i+1)%n
  175. 		allAns<<searchB(0,n,p1,0.0,1.0,xs,ys,allS)
  176. 	}
  177. 	allAns.select!{|e|
  178. 		(e[0].nan?)?false:true
  179. 	}
  180. 	e1=allAns.min
  181. 	#p e1[0]
  182. 	puts sprintf("%0.15f %0.15f",e1[1],e1[2])
  183. end
  184. n=1
  185. while n>0
  186. 	n=gets.to_i
  187. 	break if n==0
  188. 	f(n)
  189. end
Success #stdin #stdout 0.67s 10132KB
comments (?)
stdin
copy 
9
-97 49
-91 -73
-83 -78
-40 -99
40 -92
91 -66
80 28
-3 71
-59 63
9
-73 -67
-49 -85
13 -90
94 -95
88 69
21 68
-58 60
-67 55
-71 -10
10
-97 62
-79 -84
-72 -99
34 -100
81 -94
83 -74
84 26
72 87
41 99
-78 88
10
-96 -88
48 -98
87 -44
98 -1
77 36
35 89
0 100
-47 91
-89 43
-92 -5
6
-88 -75
87 -74
74 93
2 92
-65 82
-82 62
7
-93 -15
-29 -88
79 -91
100 31
89 85
36 95
-2 74
9
-97 45
-80 -16
25 -97
34 -97
91 -54
94 -38
90 51
49 71
17 77
7
-79 -36
-63 -71
-2 -89
37 -88
60 -63
87 77
-76 84
6
-100 -99
66 -88
88 -24
47 89
-48 90
-86 33
8
-75 -59
-20 -98
2 -97
85 -62
94 -33
94 19
25 91
-56 85
9
-98 -14
-66 -95
51 -85
87 -78
90 -32
91 36
-23 95
-82 98
-95 33
7
-77 52
-62 -95
22 -77
100 -35
81 26
34 81
-75 98
9
-99 -14
-86 -86
-48 -88
50 -85
91 -76
85 57
62 71
22 84
-52 73
7
-91 11
-84 -95
84 -92
96 12
90 47
70 98
-79 58
7
-93 -9
-90 -83
-47 -84
44 -68
95 35
5 82
-25 64
7
-90 -85
-10 -89
66 -27
90 11
79 56
45 98
-81 59
10
-83 74
-55 -62
-49 -76
-11 -95
46 -89
94 -51
90 28
76 46
-2 100
-66 95
9
-89 4
-76 -91
-33 -100
78 -88
84 -52
92 1
81 93
1 100
-60 65
7
-87 -89
30 -99
91 -83
96 71
-37 60
-83 1
-85 -19
7
-93 46
-92 -50
-12 -87
27 -95
84 -64
100 -31
96 91
9
-85 -59
-55 -56
83 -23
84 20
70 92
51 97
33 100
-67 94
-85 -42
7
-89 -20
27 -82
69 -72
82 -45
100 66
78 83
-41 95
10
-100 -63
69 -71
74 -67
81 -57
98 3
81 31
45 64
-54 91
-95 94
-100 40
9
-99 51
-92 -67
-78 -100
-28 -99
78 -65
92 37
37 87
-49 82
-97 75
8
-84 -13
-74 -68
-5 -96
98 -46
94 10
83 83
79 85
-81 100
11
-92 20
-89 -65
4 -92
45 -65
85 -26
94 7
96 73
-25 100
-66 90
-85 79
-91 53
7
-95 91
-74 -37
-54 -96
18 -98
88 -44
97 -5
94 97
8
-82 68
-61 -55
-32 -97
93 -29
88 -3
62 31
21 82
3 94
6
-100 -85
-50 -85
61 -80
87 61
-92 96
-99 8
8
-97 -17
-76 -77
-72 -85
48 -84
72 -33
99 74
60 88
-33 98
8
-82 -16
-8 -90
66 -94
85 -74
94 25
79 95
-29 95
-56 93
8
-94 48
-90 -25
-70 -48
92 -89
100 56
90 84
1 100
-35 93
8
-90 35
-17 -89
27 -99
94 -42
100 61
-9 98
-77 91
-89 63
8
-99 -37
-30 -96
58 -99
92 85
66 93
23 91
-77 78
-92 44
10
-99 -64
-65 -68
-8 -70
26 -66
87 -55
87 -21
86 51
55 90
-79 95
-96 87
7
-96 -29
-90 -83
92 -53
86 56
75 88
-21 89
-44 72
10
-98 24
-78 -18
-21 -83
25 -94
45 -81
80 0
94 72
83 80
57 95
-92 58
10
-98 -57
-45 -96
80 -93
89 -68
100 -23
87 27
49 55
-12 83
-66 39
-98 -4
11
-95 4
-92 -46
-79 -80
22 -93
68 -71
85 -35
85 29
57 92
35 94
-18 89
-95 22
8
-97 -47
-65 -99
76 -95
96 57
63 76
20 100
-73 28
-82 0
8
-87 -40
-6 -96
5 -96
91 -68
100 -42
75 58
-11 69
-62 61
10
-91 21
-81 -19
-55 -43
86 -87
94 -58
91 -35
73 13
25 69
-14 87
-90 94
9
-93 12
-68 -71
70 -49
99 -36
42 90
15 98
-40 100
-83 57
-88 37
8
-100 -48
-91 -100
90 -74
81 66
72 78
63 86
-50 87
-86 78
9
-96 -47
-95 -99
52 -97
74 -92
88 -37
91 -8
56 100
-80 89
-89 81
5
-91 -94
70 -94
3 40
-45 94
-91 -26
7
-93 -64
8 -80
77 -84
84 -76
73 58
-71 98
-89 -10
10
-100 75
-46 -63
18 -92
75 -100
100 -72
92 -38
70 23
35 59
-24 88
-79 96
11
-94 -29
20 -86
25 -85
92 -64
82 -14
79 -3
57 36
40 57
-59 100
-88 85
-92 64
8
-94 34
-85 -65
-68 -79
-48 -85
50 -80
86 28
28 78
-49 97
7
-94 100
-70 -65
-30 -89
51 -97
89 -64
82 83
81 84
8
-97 93
-85 -90
-33 -86
19 -79
57 -63
63 -6
72 90
-5 93
9
-100 46
-87 -77
-16 -92
52 -100
57 -93
96 -36
91 37
63 89
-78 98
10
-96 -28
-16 -81
15 -93
68 -77
85 -68
85 -7
41 92
12 87
-81 67
-94 6
8
-100 37
-81 -100
-66 -100
38 -74
82 -16
82 22
59 61
-93 84
12
-100 -52
-89 -79
-5 -91
30 -95
49 -88
68 15
51 78
20 78
-31 68
-66 60
-77 53
-94 -18
9
-91 3
-77 -61
-67 -99
34 -84
90 -54
90 16
64 82
6 89
-76 19
8
-99 13
-82 -56
-12 -99
27 -90
87 32
66 88
-74 93
-94 82
7
-99 65
-89 -80
48 -95
79 79
75 91
4 99
-94 90
9
-77 40
-71 -87
8 -100
83 -93
93 -72
98 -59
96 64
80 82
-43 56
10
-81 -60
-72 -87
-61 -90
76 -99
90 -58
95 9
68 80
57 96
6 83
-71 57
11
-92 -35
-88 -78
-33 -94
60 -77
100 -62
85 12
28 72
2 88
-50 56
-83 35
-85 30
0
stdout
copy 
28.917327009442126 54.464517332457689
90.779728543131540 -94.801217811304411
-80.816624657376025 -69.265155556838920
60.562612369984812 56.742417723590592
0.597180757205933 91.790623993612826
86.901988106103232 -45.093211955019299
91.445523352862097 18.837105398818238
61.623718149665400 -54.580720705438658
59.538354477530490 54.443071805830598
92.462479426059872 -37.954232960473746
-74.109536765794317 -74.472735061583137
52.115654670300167 59.800829641138101
27.761795223595222 -85.680761370706264
-42.535785234402510 67.789050943784559
50.484686707559867 58.246885830496510
53.033802070167027 -37.577687784863734
90.529742004349828 17.537595414090902
-63.810365545664226 56.985093162568347
55.283995384898333 -92.368132358059455
75.628162366803735 -68.553104677703232
-12.420355396345258 97.274778676219285
83.018856418319046 79.121792767662555
-97.905119800045426 62.624706159509529
76.002552356606927 51.543134221266428
-43.812965752320714 -80.249810999058255
42.573227770248650 -66.598118297641136
94.172435935667679 91.137178187299028
-58.510801727417856 75.184931236319244
-99.056437275257338 2.751333401067841
-18.634777704316804 -84.555289814202638
-57.843830075428230 -40.156169924571763
68.323437106329948 87.896910183131695
90.822464675838418 64.115310155908062
72.261349509770866 -21.820932064769480
-66.609022622524023 94.537650097855376
31.177136018872261 88.456488166470081
69.086739516817033 88.026881047990173
-13.250557995704204 81.981026818315087
71.752505212177965 58.806863272599607
61.666667384818894 -95.406619364969671
62.077862266912412 -77.416509959609911
27.727710758542806 -68.815739527488546
-35.743016989436001 99.845200617797673
82.117460015970437 48.617288640459712
-95.536178553011268 -71.118715243414044
-91.000000000000000 -88.926013359799981
-91.129330342635512 -38.745959625579417
44.798166565631810 -95.761146184650073
-93.020326193174839 16.554832017370419
73.381605607734514 -9.855183176796505
77.780413615116913 84.294362183760740
59.825358100694928 -36.159098043398195
81.650663274913683 -56.972107521280023
-17.002668795077934 80.762866925789695
74.634425703901798 34.489452067296952
61.215145978275871 40.143870786389421
-38.951870081326540 50.626452369599292
-94.907533958088607 69.476031378377229
59.093641561495296 -32.732463493542518
-48.584759366164938 53.371877945334141
-54.426997490991134 62.596078769275728
32.417487145392919 67.350013531165345
https://ideone.com/gXotfE
language:
Ruby (ruby 2.5.5)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!