fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. #define sqr(x) ((x)*(x))
  22. using namespace std;
  23.  
  24. typedef long long LL;
  25. typedef double ld;
  26.  
  27. const int MAX=10000+10;
  28.  
  29. struct Point
  30. {
  31. 	int x,y,r;
  32. }d[MAX];
  33.  
  34. int n;
  35. pair<ld,ld> toWork[MAX];
  36.  
  37. int check(int Num)
  38. {
  39. 	const static ld INF=1e5;
  40. 	ld left=-INF,right=INF;
  41. 	int i;
  42. 	REP(i,1,Num)
  43. 	{
  44. 		left=max(left,(ld)d[i].x-d[i].r);
  45. 		right=min(right,(ld)d[i].x+d[i].r);
  46. 	}
  47. 	if(left>right)
  48. 		return 0;
  49. 	for(int T=20;T--;)
  50. 	{
  51. 		ld mid=(left+right)*0.5;
  52. 		int top=0;
  53. 		REP(i,1,Num)
  54. 		{
  55. 			ld delta= sqrt ( sqr( d[i].r ) - sqr( mid - d[i].x ) );
  56. 			toWork[top++]=mp(d[i].y-delta,d[i].y+delta);
  57. 		}
  58. 		ld ll=-INF,rr=INF;
  59. 		int l=0,r=0;
  60. 		REP2(i,0,Num)
  61. 		{
  62. 			if(ll<toWork[i].x)
  63. 			{
  64. 				ll=toWork[i].x;
  65. 				l=i;
  66. 			}
  67. 			if(rr>toWork[i].y)
  68. 			{
  69. 				rr=toWork[i].y;
  70. 				r=i;
  71. 			}
  72. 		}
  73. 		if(ll<=rr)
  74. 			return 1;
  75. 		ld dist=sqrt(sqr(d[l].x-d[r].x)+sqr(d[l].y-d[r].y));
  76. 		if(dist > d[l].r+d[r].r )
  77. 			return 0;
  78. 		ld angle=atan2(d[r].y-d[l].y,d[r].x-d[l].x);
  79. 		ld the=( sqr(dist)+sqr(d[l].r)-sqr(d[r].r) ) / (2 * dist * d[l].r);
  80. 		ld nx=d[l].x+cos(angle-the)*d[l].r;
  81. 		if(nx<=mid)
  82. 			right=mid;
  83. 		else left=mid;
  84. 	}
  85. 	return 0;
  86. }
  87.  
  88. int main()
  89. {
  90. 	int i;
  91. 	scanf("%d",&n);
  92. 	REP(i,1,n)
  93. 		scanf("%d%d%d",&d[i].x,&d[i].y,&d[i].r);
  94. 	int Left=1,Right=n;
  95. 	while(Left<Right)
  96. 	{
  97. 		int Mid=(Left+Right+1)/2;
  98. 		if(check(Mid))
  99. 			Left=Mid;
  100. 		else Right=Mid-1;
  101. 	}
  102. 	if(Left==n)
  103. 		printf("NIE\n");
  104. 	else printf("%d\n",Left+1);
  105. 	return 0;
  106. }
Success #stdin #stdout 0s 3572KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
https://ideone.com/IJaWY5
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

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!