fork(1) download 
  1. def g(x1,y1,x2,y2)
  2. 	return x1*y2-y1*x2
  3. end
  4.  
  5. def lenCheck(x,y)
  6. 	dx=((x.negative?)?-1:1)*0.0000001
  7. 	dy=((y.negative?)?-1:1)*0.0000001
  8. 	add=0
  9. 	while x*x+y*y<1.0 && add<100
  10. 		x+=dx
  11. 		y+=dy
  12. 		add+=1
  13. 	end
  14.  
  15. 	return [x,y]
  16. end
  17.  
  18. def searchP(x1,y1,xs,ys,n)
  19. 	res=0
  20. 	n.times{|i|
  21. 		p1=i
  22. 		p2=(i+1)%n
  23. 		if 0<=g(xs[p1],ys[p1],-x1,-y1) && 0<=g(-x1,-y1,xs[p2],ys[p2]) then
  24. 			res=i
  25. 			break	
  26. 		end
  27. 	}
  28. 	return res
  29. end
  30.  
  31. def calcAllS(xs,ys,n)
  32. 	ans=0.0
  33. 	n.times{|i|
  34. 		x1=xs[i]
  35. 		y1=ys[i]
  36. 		x2=xs[(i+1)%n]
  37. 		y2=ys[(i+1)%n]
  38. 		ans+=g(x1,y1,x2,y2)
  39. 	}
  40. 	return (ans/2.0).abs
  41. end
  42.  
  43. def calcCross(n,p1,bx,by,xs,ys)
  44. 	p2=(p1+1)%n
  45. 	dx=xs[p2]-xs[p1]
  46. 	dy=ys[p2]-ys[p1]
  47. 	ax=xs[p1]
  48. 	ay=ys[p1]
  49. 	t=(by*ax-bx*ay)/(bx*dy-dx*by)
  50. 	rx=ax+t*dx
  51. 	ry=ay+t*dy
  52. 	return [rx,ry]
  53. end
  54.  
  55. def calcS(deep,n,p1,r1,r2,xs,ys)
  56. 	r3=(r1+r2)/2.0
  57. 	r1a=(r1+r3)/2.0
  58.  
  59. 	bx=xs[p1]*(1.0-r1a)+xs[(p1+1)%n]*r1a
  60. 	by=ys[p1]*(1.0-r1a)+ys[(p1+1)%n]*r1a
  61. 	p2=searchP(bx,by,xs,ys,n)
  62.  
  63. 	ax=xs[p2]
  64. 	ay=ys[p2]
  65. 	dx=xs[(p2+1)%n]-xs[p2]
  66. 	dy=ys[(p2+1)%n]-ys[p2]
  67. 	xy=calcCross(n,p2,bx,by,xs,ys)
  68. 	areaXs=[]
  69. 	areaYs=[]
  70. 	p1a=[p1,p2].min
  71. 	p2a=[p1,p2].max
  72.  
  73. 	n.times{|i|
  74. 		if p1a<i && i<=p2a then
  75. 			areaXs<<xs[i]
  76. 			areaYs<<ys[i]
  77. 		end
  78. 	}
  79. 	if p1<p2 then
  80. 		areaXs.unshift(bx)
  81. 		areaYs.unshift(by)
  82. 		areaXs<<xy[0]
  83. 		areaYs<<xy[1]
  84. 	else
  85. 		areaXs.unshift(xy[0])
  86. 		areaYs.unshift(xy[1])
  87. 		areaXs<<bx
  88. 		areaYs<<by
  89. 	end
  90.  
  91. 	#p [bx,by,xy[0],xy[1]]
  92. 	areaS=calcAllS(areaXs,areaYs,areaXs.size)
  93. 	#p ["s",areaS,areaS*2] if(deep==32)
  94. 	return areaS
  95. end
  96.  
  97. def searchB(deep,n,p1,r1,r2,xs,ys,allS)
  98. 	r3=(r1+r2)/2.0
  99.  
  100. 	if 30<deep then
  101. 		rx0=xs[p1]*(1.0-r3)+xs[(p1+1)%n]*r3
  102. 		ry0=ys[p1]*(1.0-r3)+ys[(p1+1)%n]*r3
  103. 		rxy0=lenCheck(rx0,ry0)
  104. 		rx=rxy0[0]
  105. 		ry=rxy0[1]
  106. 		s0=calcS(deep,n,p1,r3,r3,xs,ys)
  107. 		rd=(allS-s0*2).abs
  108. 		return [rd,rx,ry]
  109. 	else
  110. 		s1=calcS(deep,n,p1,r1,r2,xs,ys)
  111. 		d1=(s1-(allS-s1)).abs
  112. 		s2=calcS(deep,n,p1,r2,r1,xs,ys)
  113. 		d2=(s2-(allS-s2)).abs
  114. 		if d1<d2 then
  115. 			return searchB(deep+1,n,p1,r1,r3,xs,ys,allS)
  116. 		else
  117. 			return searchB(deep+1,n,p1,r3,r2,xs,ys,allS)
  118. 		end
  119. 	end
  120. end
  121. def f(n)
  122. 	xs=[]
  123. 	ys=[]
  124. 	xs0=[]
  125. 	ys0=[]
  126.  
  127. 	n.times{
  128. 		x,y=gets.split(" ").map{|e| e.to_f}
  129. 		xs<<x
  130. 		ys<<y
  131. 		xs0<<x
  132. 		ys0<<y
  133. 	}
  134. 	allS=calcAllS(xs,ys,n)
  135. 	xs0.size.times{|p1|
  136. 		n=xs.size
  137. 		bx=xs0[p1]
  138. 		by=ys0[p1]
  139. 		p2=searchP(bx,by,xs,ys,n)
  140. 		ax=xs[p2]
  141. 		ay=ys[p2]
  142. 		dx=xs[(p2+1)%n]-xs[p2]
  143. 		dy=ys[(p2+1)%n]-ys[p2]
  144. 		xy=calcCross(n,p2,bx,by,xs,ys)
  145. 		xs.insert(p2+1,xy[0])
  146. 		ys.insert(p2+1,xy[1])
  147. 	}
  148. 	n=xs.size
  149. 	allAns=[]
  150. 	n.times{|i|
  151. 		p1=i
  152. 		p2=(i+1)%n
  153. 		allAns<<searchB(0,n,p1,0.0,1.0,xs,ys,allS)
  154. 	}
  155. 	e1=allAns.min
  156. 	p e1[0]
  157. 	#puts sprintf("%0.15f %0.15f",e1[1],e1[2])
  158. end
  159. n=1
  160. while n>0
  161. 	n=gets.to_i
  162. 	break if n==0
  163. 	f(n)
  164. end
Success #stdin #stdout 0.2s 10792KB
comments (?)
stdin 
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
0
stdout 
3.1029776437208056e-07
1.2245436664670706e-08
2.2741005523130298e-08
4.3502586777321994e-07
1.1537849786691368e-07
6.660411600023508e-08
2.996239345520735e-08
4.075081960763782e-07
1.3183380360715091e-06
2.6277120923623443e-07
2.1087907953187823e-07
1.1285737855359912e-07
4.969115252606571e-08
https://ideone.com/GxNIrt
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!