fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef long double ld;
  7.  
  8. struct point {
  9. int x, y, index;
  10. bool joined, isfault;
  11. point() {}
  12. point(int a, int b) {
  13. x = a, y = b;
  14. }
  15. bool operator < (point other) {
  16. return y < other.y || (y == other.y && x < other.x);
  17. }
  18. bool onSegment(point a, point b) {
  19. if (ccw(a, b) != 0) {
  20. return false;
  21. }
  22. int minx = min(a.x, b.x);
  23. int maxx = max(a.x, b.x);
  24. int miny = min(a.y, b.y);
  25. int maxy = max(a.y, b.y);
  26. return minx <= x && x <= maxx && miny <= y && y <= maxy;
  27. }
  28. int updown() {
  29. if (y < 0 || (y == 0 && x > 0)) {
  30. return 0;
  31. }
  32. return 1;
  33. }
  34. int ccw(point a, point b) {
  35. ll c = (ll)x * (a.y - b.y) + (ll)a.x * (b.y - y) + (ll)b.x * (y - a.y);
  36. if (c == 0) {
  37. return 0;
  38. }
  39. if (c > 0) {
  40. return 1;
  41. }
  42. return - 1;
  43. }
  44. ld dist(point other) {
  45. return hypot(x - other.x, y - other.y);
  46. }
  47. };
  48.  
  49. point O = point(0, 0);
  50.  
  51. bool cmp(point a, point b) {
  52. if (a.updown() != b.updown()) {
  53. return a.updown() < b.updown();
  54. }
  55. return (ll)a.y * b.x < (ll)a.x * b.y;
  56. }
  57.  
  58. vector <point> Build_ConvexHull(vector <point> &p) {
  59. vector <point> ans;
  60. sort(p.begin(), p.end());
  61. bool checking = true;
  62. for (int i = 0; i < p.size(); ++i) {
  63. if (p[0].ccw(p[1], p[i]) != 0) {
  64. checking = false;
  65. break;
  66. }
  67. }
  68. if (checking == true) {
  69. ans = p;
  70. p.clear();
  71. return ans;
  72. }
  73.  
  74. for (int i = 0; i < p.size(); ++i) {
  75. p[i].index = i;
  76. p[i].joined = false;
  77. }
  78. vector <point> pts = p;
  79. int n = p.size(), sz = 0;
  80. p.resize(n + 1);
  81. for (int i = 1; i < n; ++i) {
  82. if (i == n - 1 || pts[0].ccw(pts[i], pts[n - 1]) >= 0) {
  83. while (sz > 0 && p[sz - 1].ccw(p[sz], pts[i]) < 0) {
  84. sz--;
  85. }
  86. p[++sz] = pts[i];
  87. }
  88. }
  89. if (sz != n - 1) {
  90. for (int i = n - 2, j = sz; i >= 0; --i) {
  91. if (i == 0 || pts[n - 1].ccw(pts[i], pts[0]) >= 0) {
  92. while (sz > j && p[sz - 1].ccw(p[sz], pts[i]) < 0) {
  93. sz--;
  94. }
  95. p[++sz] = pts[i];
  96. }
  97. }
  98. p.resize(sz);
  99. }
  100. else {
  101. p.resize(sz + 1);
  102. }
  103.  
  104. for (int i = 0; i < p.size(); ++i) {
  105. pts[p[i].index].joined = true;
  106. }
  107. ans = p;
  108. p.clear();
  109. for (auto i : pts) {
  110. if (i.joined == false) {
  111. p.push_back(i);
  112. }
  113. }
  114.  
  115. return ans;
  116. }
  117.  
  118. int main() {
  119. ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
  120. if (fopen("test.inp", "r")) {
  121. freopen("test.inp", "r", stdin);
  122. freopen("test.out", "w", stdout);
  123. }
  124.  
  125. int T;
  126. cin >> T;
  127. while (T--) {
  128. int n;
  129. cin >> n;
  130. vector <point> p(n);
  131. for (int i = 0; i < n; ++i) {
  132. cin >> p[i].x >> p[i].y;
  133. }
  134. vector <point> points = p;
  135. p.push_back(O);
  136. ld ans = 0;
  137.  
  138. vector <vector <point>> pp(2);
  139. pp[0] = Build_ConvexHull(p);
  140. p.push_back(O);
  141. pp[1] = Build_ConvexHull(p);
  142.  
  143. if (pp[0].size() + pp[1].size() == n + 2) {
  144. bool checking = true;
  145. for (int i = 0; i < 2; ++i) {
  146. if (pp[i].size() < 3) {
  147. checking = false;
  148. break;
  149. }
  150. bool contain = false;
  151. for (int j = 0; j < pp[i].size(); ++j) {
  152. if (pp[i][j].x == 0 && pp[i][j].y == 0) {
  153. contain = true;
  154. }
  155. int pre = (j - 1 + pp[i].size()) % pp[i].size();
  156. int nxt = (j + 1) % pp[i].size();
  157. if (pp[i][pre].ccw(pp[i][j], pp[i][nxt]) == 0) {
  158. checking = false;
  159. break;
  160. }
  161. }
  162. if (contain == false) {
  163. checking = false;
  164. }
  165. if (checking == false) {
  166. break;
  167. }
  168. }
  169. if (checking == true) {
  170. for (int i = 0; i < 2; ++i) {
  171. for (int j = 0; j < pp[i].size(); ++j) {
  172. int nxt = (j + 1) % pp[i].size();
  173. ans += pp[i][j].dist(pp[i][nxt]);
  174. }
  175. }
  176. }
  177. }
  178.  
  179. p = points;
  180. sort(p.begin(), p.end(), cmp);
  181. int pos = - 1;
  182. bool checking = true;
  183. for (int i = 0; i < n; ++i) {
  184. int nxt = (i + 1) % n;
  185. if (p[i].onSegment(O, p[nxt]) || p[nxt].onSegment(O, p[i])) {
  186. checking = false;
  187. break;
  188. }
  189. }
  190. if (checking == true) {
  191. for (int i = 0; i < n; ++i) {
  192. int pre = (i - 1 + n) % n;
  193. int nxt = (i + 1) % n;
  194. if (p[pre].ccw(p[i], p[nxt]) < 0 || p[i].onSegment(p[pre], p[nxt])) {
  195. p[i].isfault = true;
  196. }
  197. else {
  198. p[i].isfault = false;
  199. }
  200. p[i].index = i;
  201. }
  202.  
  203. vector <deque <point>> pts(2);
  204. vector <ld> len(2, 0);
  205. vector <int> fault(2);
  206. vector <bool> status(2, true);
  207. pts[0].push_back(p[0]);
  208. for (int i = 1; i < n; ++i) {
  209. if (p[0].ccw(O, p[i]) < 0) {
  210. len[0] += pts[0].back().dist(p[i]);
  211. if (pts[0].size() >= 2 && pts[0].back().isfault == true) {
  212. status[0] = false;
  213. fault[0] = pts[0].back().index;
  214. }
  215. pts[0].push_back(p[i]);
  216. }
  217. else {
  218. if (pts[1].size()) {
  219. len[1] += pts[1].back().dist(p[i]);
  220. }
  221. if (pts[1].size() >= 2 && pts[1].back().isfault == true) {
  222. status[1] = false;
  223. fault[1] = pts[1].back().index;
  224. }
  225. pts[1].push_back(p[i]);
  226. }
  227. }
  228. if ((status[0] && pts[0].size() >= 2 && O.ccw(pts[0].front(), pts[0].back()) > 0) && (status[1] && pts[1].size() >= 2 && O.ccw(pts[1].front(), pts[1].back()) > 0)) {
  229. ans = max(ans, len[0] + O.dist(pts[0].front()) + O.dist(pts[0].back()) + len[1] + O.dist(pts[1].front()) + O.dist(pts[1].back()));
  230. }
  231.  
  232. for (int i = 1; i < n; ++i) {
  233. point curr = pts[0].front();
  234. if (pts[1].size()) {
  235. len[1] += pts[1].back().dist(curr);
  236. }
  237. if (pts[1].size() >= 2 && pts[1].back().isfault == true) {
  238. status[1] = false;
  239. fault[1] = pts[1].back().index;
  240. }
  241. pts[1].push_back(curr);
  242. pts[0].pop_front();
  243. if (pts[0].size()) {
  244. len[0] -= pts[0].front().dist(curr);
  245. if (status[0] == false) {
  246. if (pts[0].front().isfault == true && pts[0].front().index == fault[0]) {
  247. status[0] = true;
  248. }
  249. }
  250. }
  251. else {
  252. pts[0].push_back(p[i]);
  253. point curr = pts[1].front();
  254. pts[1].pop_front();
  255. if (pts[1].size()) {
  256. len[1] -= pts[1].front().dist(curr);
  257. if (status[1] == false) {
  258. if (pts[1].front().isfault == true && pts[1].front().index == fault[1]) {
  259. status[1] = true;
  260. }
  261. }
  262. }
  263. }
  264.  
  265. while (pts[1].size() > 0 && p[i].ccw(O, pts[1].front()) < 0) {
  266. curr = pts[1].front();
  267. len[0] += pts[0].back().dist(curr);
  268. if (pts[0].size() >= 2 && pts[0].back().isfault == true) {
  269. status[0] = false;
  270. fault[0] = pts[0].back().index;
  271. }
  272. pts[0].push_back(curr);
  273. pts[1].pop_front();
  274. if (pts[1].size()) {
  275. len[1] -= pts[1].front().dist(curr);
  276. if (status[1] == false) {
  277. if (pts[1].front().isfault == true && pts[1].front().index == fault[1]) {
  278. status[1] = true;
  279. }
  280. }
  281. }
  282. }
  283.  
  284. if ((status[0] && pts[0].size() >= 2 && O.ccw(pts[0].front(), pts[0].back()) > 0) && (status[1] && pts[1].size() >= 2 && O.ccw(pts[1].front(), pts[1].back()) > 0)) {
  285. ans = max(ans, len[0] + O.dist(pts[0].front()) + O.dist(pts[0].back()) + len[1] + O.dist(pts[1].front()) + O.dist(pts[1].back()));
  286. }
  287. }
  288. }
  289.  
  290. cout << fixed << setprecision(10) << ans << "\n";
  291. }
  292. }
  293.  
Success #stdin #stdout 0.01s 5516KB
stdin
3
4
0 3
3 0
2 3
3 2
5
4 0
5 -5
-4 -2
1 -2
-5 -2
4
0 1
1 0
0 2
1 1
stdout
17.2111025509
36.6326947621
0.0000000000