fork(1) download 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <cstdlib>
  7. #include <vector>
  8. #include <set>
  9. #include <map>
  10. #include <queue>
  11. #include <stack>
  12. #include <list>
  13. #include <cmath>
  14. #include <iomanip>
  15. #define dibs reserve
  16. #define OVER9000 1234567890
  17. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  18. #define tisic 47
  19. #define soclose 1e-8
  20. #define chocolate win
  21. // so much chocolate
  22. #define patkan 9
  23. #define ff first
  24. #define ss second
  25. #define abs(x) ((x < 0)?-(x):x)
  26. #define uint unsigned int
  27. #define dbl long double
  28. using namespace std;
  29. // mylittledoge
  30.  
  31. struct pt {
  32. 	long long x,y;
  33.  
  34. 	bool operator<(const pt &A) const {
  35. 		if(x != A.x) return x < A.x;
  36. 		return y < A.y;}
  37. 	};
  38.  
  39. int vs(pt A, pt B, pt O) {
  40. 	return (A.x-O.x)*(B.y-O.y)-(A.y-O.y)*(B.x-O.x);}
  41.  
  42. int main() {
  43. 	cin.sync_with_stdio(0);
  44. 	cin.tie(0);
  45. 	int T;
  46. 	cin >> T;
  47. 	for(int t =0; t < T; t++) {
  48. 		int N;
  49. 		cin >> N;
  50. 		vector<pt> P0(N);
  51. 		for(int i =0; i < N; i++) cin >> P0[i].x >> P0[i].y;
  52. 		sort(P0.begin(),P0.end());
  53. 		vector<int> H[2];
  54. 		for(int i =0; i < 2; i++) H[i].push_back(0);
  55. 		for(int i =1; i < N; i++) {
  56. 			if(vs(P0[N-1],P0[i],P0[0]) >= 0) {
  57. 				while(H[0].size() > 1 && vs(P0[i],P0[*H[0].rbegin()],P0[H[0][H[0].size()-2]]) <= 0) 
  58. 					H[0].pop_back();
  59. 				H[0].push_back(i);}
  60. 			if(vs(P0[N-1],P0[i],P0[0]) <= 0) {
  61. 				while(H[1].size() > 1 && vs(P0[i],P0[*H[1].rbegin()],P0[H[1][H[1].size()-2]]) >= 0) 
  62. 					H[1].pop_back();
  63. 				H[1].push_back(i);}
  64. 			}
  65. 		vector<pt> P;
  66. 		for(int i =0; i < H[0].size(); i++) P.push_back(P0[H[0][i]]);
  67. 		for(int i =H[1].size()-2; i > 0; i--) P.push_back(P0[H[1][i]]);
  68. 		N =P.size();
  69.  
  70. 		int ans =0;
  71. 		for(int i =0; i < N; i++) {
  72. 			int a =i, b =(i+1)%N;
  73. 			for(int j =i+1; j < N; j++) {
  74. 				while((a+1)%N != j && abs(vs(P[(a+1)%N],P[j],P[i])) > abs(vs(P[a],P[j],P[i])))
  75. 					a =(a+1)%N;
  76. 				while((b+1)%N != i && abs(vs(P[(b+1)%N],P[j],P[i])) > abs(vs(P[b],P[j],P[i])))
  77. 					b =(b+1)%N;
  78. 				ans =max(ans,abs(vs(P[a],P[j],P[i]))+abs(vs(P[b],P[j],P[i])));
  79. 				if(b == j) b =(b+1)%N;}
  80. 			}
  81.  
  82. 		cout << ans/2 << ((ans%2 != 0)?".5":"") << "\n";}
  83. 	return 0;}
  84.  
  85. // look at my code
  86. // my code is amazing
Success #stdin #stdout 0s 3484KB
comments (?)
stdin 
3
6
0 0
3 7
10 0
11 6
0 10
10 10
5
0 0
-2 -2
3 -2
0 1
0 3
10
3 1
4 1
5 9
2 6
5 3
5 8
9 7
9 3
2 3
8 4
stdout 
100
12.5
31
https://ideone.com/ZoFQek
CT S02E08 C
language:
C++14 (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!