fork download
copy 
  1. /******************************************
  2. *    AUTHOR:         CHIRAG AGARWAL       *
  3. *    INSTITUITION:   BITS PILANI, PILANI  *
  4. ******************************************/
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. typedef long long LL; 
  9. typedef long double LD;
  10. const int MAX=2e5+5;
  11. const long double eps=1e-20;
  12.  
  13. struct Point
  14. {
  15. 	LL x,y;
  16. 	int ind;
  17.  
  18. 	Point(LL a,LL b)
  19. 	{
  20. 		x=a;
  21. 		y=b;
  22. 	}
  23.  
  24. 	Point(){}
  25.  
  26. 	Point operator +(const Point &a)
  27. 	{
  28. 		return Point(a.x+x,a.y+y);
  29. 	}
  30.  
  31. 	Point operator -(const Point &a)
  32. 	{
  33. 		return Point(x-a.x,y-a.y);
  34. 	}
  35. };
  36.  
  37.  
  38. LL cross(Point a,Point b)
  39. {
  40. 	return ((a.x*b.y)-(b.x*a.y));
  41. }
  42.  
  43. LL dot(Point a,Point b)
  44. {
  45. 	return ((a.x*b.x)+(a.y*b.y));
  46. }
  47.  
  48. double mag(Point a)
  49. {
  50. 	return sqrt(dot(a,a));
  51. }
  52.  
  53. int ind;
  54. int n;
  55. Point arr[MAX];
  56. Point vec[MAX];
  57. LL ans[MAX];
  58. vector<Point> quad[5];
  59. Point dir[5];
  60. int ref[5];	
  61.  
  62. bool cmp(Point a,Point b)
  63. {
  64. 	return ((dot(a,dir[ind])/mag(a))>(dot(b,dir[ind])/mag(b)));	
  65. }
  66.  
  67.  
  68. Point lo;
  69.  
  70. bool scmp(Point a,Point b)
  71. {
  72. 	LL val=cross(a-lo,b-lo);
  73. 	if(val==0)
  74. 	{
  75. 		return (mag(a-lo)<mag(b-lo));
  76. 	}
  77. 	else
  78. 	{
  79. 		return val>0;
  80. 	}
  81. }
  82.  
  83. vector<Point> hull;
  84.  
  85. void get_hull()
  86. {
  87. 	int lm=1;
  88.  
  89. 	for(int i=2;i<=n;i++)
  90. 	{
  91. 		if(arr[i].x<arr[lm].x||(arr[i].x==arr[lm].x&&arr[i].y<arr[lm].y))
  92. 		{
  93. 			lm=i;
  94. 		}
  95. 	}
  96. 	lo=arr[lm];
  97.  
  98. 	swap(arr[1],arr[lm]);
  99. 	sort(arr+2,arr+n+1,scmp);
  100. 	hull.push_back(arr[1]);
  101. 	hull.push_back(arr[2]);
  102.  
  103. 	int hull_sz=2;
  104.  
  105. 	for(int i=3;i<=n;i++)
  106. 	{
  107. 		while(hull.size()>1&&cross(arr[i]-hull[hull.size()-2],hull[hull.size()-1]-hull[hull.size()-2])>0)
  108. 		{
  109. 			hull.pop_back();
  110. 			hull_sz--;
  111. 		}
  112. 		hull.push_back(arr[i]);
  113. 		hull_sz++;
  114. 	}
  115. 	int tm=0;
  116. 	int lem=0;
  117. 	int rm=0;
  118. 	int bm=0;
  119. 	for(int i=1;i<hull.size();i++)
  120. 	{
  121. 		if(hull[i].y>hull[tm].y)
  122. 		{
  123. 			tm=i;
  124. 		}
  125. 		if(hull[i].y<hull[bm].y)
  126. 		{
  127. 			bm=i;
  128. 		}
  129. 		if(hull[i].x<hull[lem].x)
  130. 		{
  131. 			lem=i;
  132. 		}
  133. 		if(hull[i].x>hull[rm].x)
  134. 		{
  135. 			rm=i;
  136. 		}
  137. 	}
  138. 	ref[1]=rm;
  139. 	ref[2]=tm;
  140. 	ref[3]=lem;
  141. 	ref[4]=bm;
  142. }
  143.  
  144. int main() 
  145. {
  146. 	int t=1;
  147. 	dir[1]=Point(1,0);
  148. 	dir[2]=Point(0,1);
  149. 	dir[3]=Point(-1,0);
  150. 	dir[4]=Point(0,-1);
  151. 	//scanf("%d",&t);
  152. 	while(t--)
  153. 	{
  154. 		for(int i=1;i<=4;i++)
  155. 		{
  156. 			quad[i].clear();
  157. 		}
  158. 		hull.clear();
  159. 		scanf("%d",&n);
  160.  
  161. 		for(int i=1;i<=n;i++)
  162. 		{
  163. 			long double a,b;
  164. 			scanf("%Lf %Lf",&a,&b);
  165. 			vec[i].x=a*1000;
  166. 			vec[i].y=b*1000;
  167. 	//			printf("%lld %lld\n",vec[i].x,vec[i].y);
  168. 			vec[i].ind=i;
  169.  
  170. 			if(vec[i].x>0&&vec[i].y>=0)
  171. 			{
  172. 				quad[1].push_back(vec[i]);
  173. 			}
  174. 			else if(vec[i].x<0&&vec[i].y<=0)
  175. 			{
  176. 				quad[3].push_back(vec[i]);
  177. 			}
  178. 			else if(vec[i].x<=0&&vec[i].y>0)
  179. 			{
  180. 				quad[2].push_back(vec[i]);
  181. 			}
  182. 			else
  183. 			{
  184. 				quad[4].push_back(vec[i]);
  185. 			}
  186. 		}
  187. 		for(int i=1;i<=4;i++)
  188. 		{
  189. 			ind=i;
  190. 			sort(quad[i].begin(),quad[i].end(),cmp);
  191. 		}	
  192.  
  193. 		for(int i=1;i<=n;i++)
  194. 		{
  195. 			arr[i]=vec[i];
  196. 		}
  197. 		if(n==1)
  198. 		{
  199. 			for(int i=1;i<=n;i++)
  200. 			{
  201. 				ans[vec[i].ind]=dot(vec[i],arr[1]);
  202. 			}
  203. 		}
  204. 		else
  205. 		{
  206. 			get_hull();
  207.  
  208. 			for(int i=1;i<=4;i++)
  209. 			{
  210. 				int ptr1=0;
  211. 				int ptr2=ref[i];
  212. 				while(ptr1<quad[i].size())
  213. 				{
  214. 					while(true)
  215. 					{
  216. 						if(dot(quad[i][ptr1],hull[(ptr2+1)%hull.size()])>dot(quad[i][ptr1],hull[ptr2]))
  217. 						{
  218. 							ptr2=(ptr2+1)%hull.size();
  219. 						}
  220. 						else
  221. 						{
  222. 							break;
  223. 						}
  224. 					}
  225. 					ans[quad[i][ptr1].ind]=dot(quad[i][ptr1],hull[ptr2]);
  226. 					ptr1++;
  227. 				}
  228. 			}	
  229. 		}
  230. 		for(int i=1;i<=n;i++)
  231. 		{
  232. 			LL tmp=ans[i];
  233. 		//	printf("%lld\n",ans[i]);
  234. 			for(int j=0;j<3;j++)
  235. 			{
  236. 				int dig=tmp%10;
  237. 				tmp/=10;
  238. 				if(dig>=5)
  239. 				{
  240. 					tmp++;
  241. 				}
  242. 			}
  243. 			int dig[3];
  244. 			for(int j=0;j<3;j++)
  245. 			{
  246. 				dig[j]=tmp%10;
  247. 				tmp/=10;
  248. 			}
  249. 			int cur=dig[2]*100+dig[1]*10+dig[0];
  250. 			printf("%lld.%.3d\n",tmp,cur);
  251. 		}
  252. 	}		
  253.  
  254. 	return 0;
  255. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
4
0.000 1.000
0.000 2.000
1.000 1.000
0.000 0.000
compilation info 
prog.cpp: In function ‘void get_hull()’:
prog.cpp:138:2: error: reference to ‘ref’ is ambiguous
  ref[1]=rm;
  ^~~
prog.cpp:60:5: note: candidates are: int ref [5]
 int ref[5];
     ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/6/bits/stdc++.h:71:0,
                 from prog.cpp:5:
/usr/include/c++/6/functional:491:5: note:                 template<class _Tp> std::reference_wrapper<_Tp> std::ref(std::reference_wrapper<_Tp>)
     ref(reference_wrapper<_Tp> __t) noexcept
     ^~~
/usr/include/c++/6/functional:483:10: note:                 template<class _Tp> void std::ref(const _Tp&&)
     void ref(const _Tp&&) = delete;
          ^~~
/usr/include/c++/6/functional:473:5: note:                 template<class _Tp> std::reference_wrapper<_Tp> std::ref(_Tp&)
     ref(_Tp& __t) noexcept
     ^~~
prog.cpp:139:2: error: reference to ‘ref’ is ambiguous
  ref[2]=tm;
  ^~~
prog.cpp:60:5: note: candidates are: int ref [5]
 int ref[5];
     ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/6/bits/stdc++.h:71:0,
                 from prog.cpp:5:
/usr/include/c++/6/functional:491:5: note:                 template<class _Tp> std::reference_wrapper<_Tp> std::ref(std::reference_wrapper<_Tp>)
     ref(reference_wrapper<_Tp> __t) noexcept
     ^~~
/usr/include/c++/6/functional:483:10: note:                 template<class _Tp> void std::ref(const _Tp&&)
     void ref(const _Tp&&) = delete;
          ^~~
/usr/include/c++/6/functional:473:5: note:                 template<class _Tp> std::reference_wrapper<_Tp> std::ref(_Tp&)
     ref(_Tp& __t) noexcept
     ^~~
prog.cpp:140:2: error: reference to ‘ref’ is ambiguous
  ref[3]=lem;
  ^~~
prog.cpp:60:5: note: candidates are: int ref [5]
 int ref[5];
     ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/6/bits/stdc++.h:71:0,
                 from prog.cpp:5:
/usr/include/c++/6/functional:491:5: note:                 template<class _Tp> std::reference_wrapper<_Tp> std::ref(std::reference_wrapper<_Tp>)
     ref(reference_wrapper<_Tp> __t) noexcept
     ^~~
/usr/include/c++/6/functional:483:10: note:                 template<class _Tp> void std::ref(const _Tp&&)
     void ref(const _Tp&&) = delete;
          ^~~
/usr/include/c++/6/functional:473:5: note:                 template<class _Tp> std::reference_wrapper<_Tp> std::ref(_Tp&)
     ref(_Tp& __t) noexcept
     ^~~
prog.cpp:141:2: error: reference to ‘ref’ is ambiguous
  ref[4]=bm;
  ^~~
prog.cpp:60:5: note: candidates are: int ref [5]
 int ref[5];
     ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/6/bits/stdc++.h:71:0,
                 from prog.cpp:5:
/usr/include/c++/6/functional:491:5: note:                 template<class _Tp> std::reference_wrapper<_Tp> std::ref(std::reference_wrapper<_Tp>)
     ref(reference_wrapper<_Tp> __t) noexcept
     ^~~
/usr/include/c++/6/functional:483:10: note:                 template<class _Tp> void std::ref(const _Tp&&)
     void ref(const _Tp&&) = delete;
          ^~~
/usr/include/c++/6/functional:473:5: note:                 template<class _Tp> std::reference_wrapper<_Tp> std::ref(_Tp&)
     ref(_Tp& __t) noexcept
     ^~~
prog.cpp: In function ‘int main()’:
prog.cpp:211:14: error: reference to ‘ref’ is ambiguous
     int ptr2=ref[i];
              ^~~
prog.cpp:60:5: note: candidates are: int ref [5]
 int ref[5];
     ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/6/bits/stdc++.h:71:0,
                 from prog.cpp:5:
/usr/include/c++/6/functional:491:5: note:                 template<class _Tp> std::reference_wrapper<_Tp> std::ref(std::reference_wrapper<_Tp>)
     ref(reference_wrapper<_Tp> __t) noexcept
     ^~~
/usr/include/c++/6/functional:483:10: note:                 template<class _Tp> void std::ref(const _Tp&&)
     void ref(const _Tp&&) = delete;
          ^~~
/usr/include/c++/6/functional:473:5: note:                 template<class _Tp> std::reference_wrapper<_Tp> std::ref(_Tp&)
     ref(_Tp& __t) noexcept
     ^~~
stdout
copy 
Standard output is empty
https://ideone.com/RU9cZ8
language:
C++ (gcc 8.3)
created:
6 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!