fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
17.2111025509
36.6326947621
0.0000000000
https://ideone.com/efo2uh
Paimon Polygon
language:
C++14 (gcc 8.3)
created:
1 year 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!