fork(1) download
copy 
  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 35<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. 	n.times{
  125. 		x,y=gets.split(" ").map{|e| e.to_f}
  126. 		xs<<x
  127. 		ys<<y
  128. 	}
  129. 	allS=calcAllS(xs,ys,n)
  130. 	allAns=[]
  131. 	n.times{|i|
  132. 		p1=i
  133. 		p2=(i+1)%n
  134. 		allAns<<searchB(0,n,p1,0.0,1.0,xs,ys,allS)
  135. 	}
  136. 	e1=allAns.sort![0]
  137. 	p [allS,e1[0]]
  138. 	#puts sprintf("%0.15f %0.15f",e1[1],e1[2])
  139. end
  140. n=1
  141. while n>0
  142. 	n=gets.to_i
  143. 	break if n==0
  144. 	f(n)
  145. end
Success #stdin #stdout 0.14s 10696KB
comments (?)
stdin
copy 
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
8
-90 76
-59 -31
-33 -96
6 -100
97 -67
96 22
62 88
35 98
7
-99 32
-87 -85
70 -80
100 51
30 73
-25 89
-83 93
7
-97 62
-67 -86
94 -82
97 26
40 79
-66 97
-87 81
8
-99 63
-80 -71
-1 -98
78 -86
100 -38
53 73
7 100
-77 100
9
-97 -8
-86 -84
-44 -95
48 -85
99 -79
75 60
56 74
-17 66
-92 57
8
-99 70
-83 -19
-61 -59
-23 -71
85 -92
100 -85
55 94
-14 96
8
-93 84
-82 -100
-46 -98
28 -64
72 -25
83 10
93 92
71 98
10
-85 -7
-44 -40
-24 -46
47 -49
73 -22
84 -2
95 76
81 98
-35 90
-49 75
7
-100 7
-99 -89
80 -83
99 -27
81 67
3 62
-69 42
8
-93 -91
29 -100
48 -93
77 -39
87 13
55 75
-21 95
-74 99
9
-96 75
-93 -6
-75 -83
5 -100
62 -52
87 20
79 47
-18 79
-55 91
8
-86 -75
80 -99
93 -47
97 14
68 84
-9 94
-84 89
-86 35
6
-100 71
-95 -48
7 -91
94 -36
80 73
54 73
8
-91 72
-71 -96
31 -95
90 -73
97 -17
100 19
77 77
17 98
8
-88 64
-86 -95
13 -90
27 -88
65 -46
97 41
-17 99
-42 93
9
-100 99
-89 -41
-74 -100
27 -73
34 -71
86 -50
93 -8
89 66
80 79
8
-92 -49
-13 -85
75 -84
85 -78
69 53
50 90
46 94
-82 92
0
stdout
copy 
[27209.5, 3.2378011383116245e-09]
[27912.0, 7.607013685628772e-09]
[25079.5, 1.2129021342843771e-08]
[27607.5, 2.3228494683280587e-08]
[28778.5, 218.09645203505352]
[28872.5, 1.0739313438534737e-08]
[30378.0, 1.737498678267002e-08]
[27617.0, 1.1968950275331736e-08]
[26862.0, 2.835440682247281e-08]
[28190.5, 1.6319972928613424e-08]
[20345.0, 6.977643352001905e-08]
[26374.5, 2.9576767701655626e-09]
[28613.5, 3.502645995467901e-08]
[25676.5, 4.212779458612204e-09]
[30717.5, 5.464244168251753e-09]
[25801.0, 3.8499028929072665]
[30783.0, 2.2540916688740253e-08]
[27051.5, 4.33369968959596e-05]
[30116.5, 2.2504536900669336e-08]
[27184.5, 9.677023626863956e-09]
https://ideone.com/sGI8Ae
language:
Ruby (ruby 2.5.5)
created:
4 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!