Advertisement
konchin_shih

e747

Jan 24th, 2021
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.18 KB | None | 0 0
  1. //Input Output
  2. #include<iostream>
  3. #include<iomanip>
  4. #include<fstream>
  5. #include<sstream>
  6. #include<streambuf>
  7. //C lib
  8. #include<cstdlib>
  9. #include<cstring>
  10. #include<cmath>
  11. #include<climits>
  12. #include<cctype>
  13. //Container
  14. #include<array>
  15. #include<vector>
  16. #include<stack>
  17. #include<queue>
  18. #include<deque>
  19. #include<list>
  20. #include<bitset>
  21. #include<set>
  22. #include<map>
  23. #include<unordered_set>
  24. #include<unordered_map>
  25. //Others
  26. #include<tuple>
  27. #include<algorithm>
  28. #include<functional>
  29. #include<numeric>
  30. #include<iterator>
  31. #include<limits>
  32. #include<utility>
  33. #include<complex>
  34. #include<type_traits>
  35. #include<initializer_list>
  36. #include<random>
  37.  
  38. using namespace std;
  39.  
  40. #if __cplusplus > 201703L
  41. #include<concepts>
  42. #include<ranges>
  43. #include<bit>
  44. #include<numbers>
  45. using namespace numbers;
  46. #include<span>
  47. #endif
  48.  
  49. void _debug() {cerr << '\n';}
  50. template <typename A, typename... B>
  51. void _debug(A a, B... b) {cerr << a << ' ', _debug(b...);}
  52. #define debug(...) cerr << '(' << (#__VA_ARGS__) << ") : ", _debug(__VA_ARGS__)
  53.  
  54. namespace abb {
  55. using ll = long long;
  56. using uint = unsigned int;
  57. using ull = unsigned long long;
  58. template<typename T> using V = vector<T>;
  59. template<typename T> using Q = queue<T>;
  60. template<typename T> using DQ = deque<T>;
  61. template<typename T> using V2d = vector<vector<T>>;
  62. template<typename T> using US = unordered_set<T>;
  63. template<typename T, size_t s> using A = array<T, s>;
  64. template<typename T1, typename T2> using UM = unordered_map<T1, T2>;
  65. template<typename T1, typename T2 = T1> using P = pair<T1, T2>;
  66. template<typename T, typename Cmp = less<T>> using S = set<T, Cmp>;
  67. template<typename T, typename Cmp = less<T>> using PQ = priority_queue<T, V<T>, Cmp>;
  68. template<typename T1, typename T2, typename Cmp = less<T1>> using M = map<T1, T2, Cmp>;
  69. template<typename T> using F = function<T>;
  70. }
  71.  
  72. namespace output {
  73. template<typename T1, typename T2>
  74. inline ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  75.     return os << '(' << p.first << ", " << p.second << ')';
  76. }
  77. #define unfold1(Container) \
  78. template<typename T> \
  79. inline ostream& operator<<(ostream& os, const Container<T>& x) { \
  80.     for (const auto& i : x) \
  81.         os << i << ' '; \
  82.     return os; \
  83. }
  84. #define unfold2(Container) \
  85. template<typename T1,typename T2> \
  86. inline ostream& operator<<(ostream& os,const Container<T1,T2>& x){ \
  87.     for (const auto& i : x) \
  88.         os << i << ' '; \
  89.     return os; \
  90. }
  91. unfold1(vector); unfold1(set); unfold1(deque); unfold2(map)
  92. #undef unfold1
  93. #undef unfold2
  94. };
  95.  
  96. namespace rit {
  97. struct fast_istream {
  98.     operator bool() const {return bool(cin);}
  99.     fast_istream() {cin.tie(nullptr);}
  100. } fin;
  101. #if __cplusplus > 201703L
  102. template<typename T>
  103. fast_istream& operator>>(fast_istream& is, T& n) requires integral<T> {
  104. #else
  105. template<typename T, class = typename enable_if<is_integral<T>::value>::type>
  106. fast_istream & operator>>(fast_istream& is, T& n) {
  107. #endif
  108.     while (isspace(cin.rdbuf()->sgetc()))
  109.         cin.rdbuf()->snextc();
  110.     bool sign = false;
  111.     if (cin.rdbuf()->sgetc() == '-')
  112.         sign = true, cin.rdbuf()->snextc();
  113.     for (n = 0; isdigit(cin.rdbuf()->sgetc());)
  114.         n *= 10, n += cin.rdbuf()->sbumpc() - '0';
  115.     n = sign ? -n : n;
  116.     return is;
  117. }
  118. fast_istream& operator>>(fast_istream& is, char& n) {
  119.     while (isspace(cin.rdbuf()->sgetc()))
  120.         cin.rdbuf()->snextc();
  121.     n = cin.rdbuf()->sbumpc();
  122.     return is;
  123. }
  124. }
  125.  
  126. #define endl '\n'
  127. namespace wit {
  128. struct fast_ostream {
  129.     operator bool() const {return bool(cout);}
  130.     fast_ostream() {cout.tie(nullptr);}
  131. } fout;
  132. constexpr int buffer_size = 30;
  133. #if __cplusplus > 201703L
  134. template<typename T>
  135. fast_ostream& operator<<(fast_ostream& os, T n) requires integral<T> {
  136. #else
  137. template<typename T, class = typename enable_if<is_integral<T>::value>::type>
  138. fast_ostream & operator<<(fast_ostream& os, T n) {
  139. #endif
  140.     if (!n) {cout.rdbuf()->sputc('0'); return os;}
  141.     if (n < 0) cout.rdbuf()->sputc('-'), n = -n;
  142.     static char buffer[buffer_size];
  143.     int cnt = buffer_size;
  144.     for (; n; n /= 10)
  145.         buffer[--cnt] = n % 10 + '0';
  146.     cout.rdbuf()->sputn(buffer + cnt, buffer_size - cnt);
  147.     return os;
  148. }
  149. fast_ostream& operator<< (fast_ostream& os, const char& n) {
  150.     cout.rdbuf()->sputc(n); return os;
  151. }
  152. }
  153.  
  154. namespace algo {
  155. template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
  156. inline void sort(T& v, function<bool(Val, Val)> cmp = less<Val>()) {sort(v.begin(), v.end(), cmp);}
  157. template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val_a, typename Val_b>
  158. inline void replace(T& v, const Val_a& a, const Val_b& b) {replace(v.begin(), v.end(), static_cast<int>(a), static_cast<int>(b));}
  159. template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type >
  160. inline _ unique(T& v, function<bool(Val, Val)> cmp = equal_to<Val>()) {return unique(v.begin(), v.end(), cmp);}
  161. template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
  162. inline _ lower_bound(T& v, const Val& x, function<bool(Val, Val)> cmp = less<Val>()) {return lower_bound(v.begin(), v.end(), x, cmp);}
  163. template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
  164. inline _ upper_bound(T& v, const Val& x, function<bool(Val, Val)> cmp = less<Val>()) {return upper_bound(v.begin(), v.end(), x, cmp);}
  165. template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
  166. inline void iota(T& v, const Val& x) {iota(v.begin(), v.end(), x);}
  167. }
  168.  
  169. //sublime autofill keywords:
  170. /*STL: push_back emplace_back pop_back push pop push_front pop_front size assign resize empty*/
  171. /*algorithm: lower_bound upper_bound equal_range next_permutation prev_permutation binary_search*/
  172. /*copy replace for_each fill find unique remove is_sorted min max min_element max_element*/
  173. /*ios: fixed setprecision setw stringstream / numeric: iota accumulate adjacent_difference partial_sum*/
  174. /*utility: move / limits: numeric_limits / iterator: begin end back_inserter front_inserter distance next prev*/
  175.  
  176. #define MULTI_TASKCASE
  177. using namespace abb;
  178. using namespace output;
  179. using namespace rit;
  180. using namespace wit;
  181. using namespace algo;
  182.  
  183. inline void init() {
  184.  
  185. }
  186.  
  187. inline ll det(P<ll> a, P<ll> b, P<ll> c) {
  188.     return a.first * b.second + b.first * c.second + c.first * a.second -
  189.            a.second * b.first - b.second * c.first - c.second * a.first;
  190. }
  191. inline ll cross(P<ll> p1, P<ll> p2, P<ll> p3) {
  192.     return (p2.first - p1.first) * (p3.second - p1.second)
  193.            - (p2.second - p1.second) * (p3.first - p1.first);
  194. }
  195. inline void solve() {
  196.     int n; cin >> n;
  197.     V<P<ll>> v(n);
  198.     for (auto& i : v)
  199.         cin >> i.first >> i.second;
  200.     sort(v.begin(), v.end());
  201.     V<P<ll>> s{v[0], v[1]};
  202.     for (int i = 2; i < n; i++) {
  203.         while (s.size() >= 2 && cross(s.rbegin()[1], s.rbegin()[0], v[i]) <= 0)
  204.             s.pop_back();
  205.         s.push_back(v[i]);
  206.     }
  207.     for (int i = n - 2, t = s.size() + 1; i >= 0; i--) {
  208.         while (int(s.size()) >= t && cross(s.rbegin()[1], s.rbegin()[0], v[i]) <= 0)
  209.             s.pop_back();
  210.         s.push_back(v[i]);
  211.     }
  212.     s.pop_back();
  213.     debug(s);
  214.     ll ans = 0;
  215.     for (int i = 0, m = s.size(); i < m; i++) {
  216.         for (int j = 1, k = 2, l = 3; k < m; k++) {
  217.             while (j < k - 1 && det(v[i], v[(i + j) % m], v[(i + k) % m]) < det(v[i], v[(i + j + 1) % m], v[(i + k) % m])) j++;
  218.             while (l < m - 1 && det(v[i], v[(i + l) % m], v[(i + k) % m]) < det(v[i], v[(i + l + 1) % m], v[(i + k) % m])) l++;
  219.             ll cur = det(v[i], v[(i + j) % m], v[(i + k) % m]) + det(v[i], v[(i + l) % m], v[(i + k) % m]);
  220.             if (cur > ans)
  221.                 ans = cur, debug(i, j, k, l);
  222.         }
  223.     }
  224.     cout << ans / 2.0 << endl;
  225. }
  226.  
  227. /*
  228. 3
  229. 5
  230. 0 0
  231. 1 0
  232. 3 1
  233. 1 2
  234. 0 1
  235. 4
  236. 0 0
  237. 4 0
  238. 0 4
  239. 1 1
  240. 4
  241. 0 0
  242. 1 1
  243. 2 2
  244. 1 1
  245. */
  246.  
  247. //#define FILEIO
  248. #ifdef FILEIO
  249. main(int, char* argv[]) {
  250.     ios::sync_with_stdio(false);
  251.     fstream filein(argv[1], ios::in);
  252.     fstream fileout(argv[2], ios::out);
  253.     cin.rdbuf(filein.rdbuf());
  254.     cout.rdbuf(fileout.rdbuf());
  255.     init();
  256.     int t = 1;
  257. #ifdef MULTI_TASKCASE
  258.     cin >> t; cin.ignore();
  259. #endif
  260.     while (t--) solve();
  261.     return 0;
  262. }
  263. #else
  264. main() {
  265.     ios::sync_with_stdio(false);
  266.     init();
  267.     int t = 1;
  268. #ifdef MULTI_TASKCASE
  269.     cin >> t; cin.ignore();
  270. #endif
  271.     while (t--) solve();
  272.     return 0;
  273. }
  274. #endif
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement