Advertisement
UPML

Untitled

May 27th, 2015
256
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.82 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <iomanip>
  6.  
  7. using namespace std;
  8.  
  9. struct point {
  10.     point(int x, int y);
  11.  
  12.     int x;
  13.     int y;
  14.  
  15.     double dist(point p) {
  16.         return sqrt(double((p.x - x) * (p.x - x) + (p.y - y) * (p.y - y)));
  17.     }
  18.  
  19.     bool operator<(const point P) const {
  20.         if (x != P.x) {
  21.             return x < P.x;
  22.         }
  23.         else {
  24.             return y < P.y;
  25.         }
  26.     }
  27.  
  28.     bool operator!=(const point P) const {
  29.         return P.x != x || P.y != y;
  30.     }
  31.  
  32.     bool operator==(const point P) const {
  33.         return P.x == x && P.y == y;
  34.     }
  35.  
  36.     void print() {
  37.         cout << x << " " << y << endl;
  38.     }
  39. };
  40.  
  41. int vectorMult(point a, point b, point c) {
  42.     return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
  43. }
  44.  
  45. int square(vector<point> &shell) {
  46.     int sum = 0;
  47.     for (int i = 2; i < shell.size(); ++i) {
  48.         sum += vectorMult(shell[0], shell[i - 1], shell[i]);
  49.     }
  50.     return (sum);
  51. }
  52.  
  53. double perim(vector<point> &shell) {
  54.     double answer = 0;
  55.     for (int i = 1; i < shell.size(); ++i) {
  56.         answer += shell[i].dist(shell[i - 1]);
  57.     }
  58.     answer += shell[0].dist(shell[shell.size() - 1]);
  59.     return answer;
  60. }
  61.  
  62. int squareWithoutI(vector<point> &shell, int i, int sum) {
  63.     if (i != 0) {
  64.         return sum - vectorMult(shell[0], shell[i - 1], shell[i]) -
  65.                 vectorMult(shell[0], shell[i], shell[i + 1]) +
  66.                 vectorMult(shell[0], shell[i - 1], shell[i + 1]);
  67.     }
  68.     else {
  69.         return sum - vectorMult(shell[shell.size() - 1], shell[0], shell[1]);
  70.     }
  71. }
  72.  
  73. int main() {
  74.     /*freopen("input.txt", "r", stdin);
  75.     freopen("output.txt", "w", stdout);
  76.     */
  77.  
  78.     int n = 0;
  79.     cin >> n;
  80.     while (n != 0) {
  81.         vector<point> arrayPoints;
  82.         for (int i = 0; i < n; ++i) {
  83.             int x, y;
  84.             cin >> x >> y;
  85.             arrayPoints.push_back(point(x, y));
  86.         }
  87.         sort(arrayPoints.begin(), arrayPoints.end());
  88.         int fl = 0;
  89.         int answer = 0;
  90.         /*    for(int i = 0; i < arrayPoints.size(); ++i){
  91.             arrayPoints[i].print();
  92.         }
  93.         cout  << endl;
  94.       */
  95.         vector<point> up, down;
  96.         up.push_back(arrayPoints[0]);
  97.         up.push_back(arrayPoints[1]);
  98.         down.push_back(arrayPoints[arrayPoints.size() - 1]);
  99.         down.push_back(arrayPoints[arrayPoints.size() - 2]);
  100.         for (int i = 2; i < arrayPoints.size(); ++i) {
  101.             while (up.size() >= 2 && vectorMult(up[up.size() - 2], up[up.size() - 1], arrayPoints[i]) <= 0) {
  102.                 up.erase(up.end());
  103.             }
  104.             up.push_back(arrayPoints[i]);
  105.         }
  106.  
  107.         for (int i = arrayPoints.size() - 2; i >= 0; --i) {
  108.             while (down.size() >= 2 && vectorMult(down[down.size() - 2], down[down.size() - 1], arrayPoints[i]) <= 0) {
  109.                 down.erase(down.end());
  110.             }
  111.             down.push_back(arrayPoints[i]);
  112.         }
  113.  
  114.         vector<point> shell;
  115.         shell = up;
  116.         for (int i = 1; i < down.size() - 1; ++i) {
  117.             shell.push_back(down[i]);
  118.         }
  119.  
  120.         int sum = answer = square(shell);
  121.  
  122.         int currentPointNumber = 0;
  123.         for (int i = 1; i < up.size() - 1; ++i) {
  124.             vector<point> added;
  125.             added.push_back(up[i - 1]);
  126.             currentPointNumber++;
  127.             if (arrayPoints[currentPointNumber] == up[i]) {
  128.                 currentPointNumber++;
  129.             }
  130.             added.push_back(arrayPoints[currentPointNumber]);
  131.             if (arrayPoints[currentPointNumber] != up[i + 1]) {
  132.                 currentPointNumber++;
  133.             }
  134.  
  135.             while (up[i + 1] != arrayPoints[currentPointNumber]) {
  136.                 if (arrayPoints[currentPointNumber] == up[i]) {
  137.                     currentPointNumber++;
  138.                 }
  139.                 if (arrayPoints[currentPointNumber] == up[i + 1]) {
  140.                     break;
  141.                 }
  142.                 while (added.size() >= 2 && vectorMult(added[added.size() - 2], added[added.size() - 1], arrayPoints[currentPointNumber]) <= 0) {
  143.                     added.erase(added.end());
  144.                 }
  145.                 if (arrayPoints[currentPointNumber] != up[i]) {
  146.                     added.push_back(arrayPoints[currentPointNumber]);
  147.                 }
  148.                 currentPointNumber++;
  149.             }
  150.             int squareTmp = -vectorMult(shell[0], up[i - 1], up[i]) - vectorMult(shell[0], up[i], up[i + 1]);
  151.             while (added.size() >= 2 && vectorMult(added[added.size() - 2], added[added.size() - 1], arrayPoints[currentPointNumber]) <= 0) {
  152.                 added.erase(added.end());
  153.             }
  154.             added.push_back(up[i + 1]);
  155.             for (int j = 1; j < added.size(); ++j) {
  156.                 squareTmp += vectorMult(shell[0], added[j - 1], added[j]);
  157.             }
  158.             answer = min(answer, sum + squareTmp);
  159.             while (arrayPoints[currentPointNumber] != up[i]) {
  160.                 currentPointNumber--;
  161.             }
  162.         }
  163.  
  164.         currentPointNumber = arrayPoints.size() - 1;
  165.         for (int i = 1; i < down.size() - 1; ++i) {
  166.             vector<point> added;
  167.             added.push_back(down[i - 1]);
  168.             currentPointNumber--;
  169.             if (arrayPoints[currentPointNumber] == down[i]) {
  170.                 currentPointNumber--;
  171.             }
  172.             added.push_back(arrayPoints[currentPointNumber]);
  173.  
  174.             if (arrayPoints[currentPointNumber] != down[i + 1]) {
  175.                 currentPointNumber--;
  176.             }
  177.  
  178.             while (down[i + 1] != arrayPoints[currentPointNumber]) {
  179.                 if (arrayPoints[currentPointNumber] == down[i]) {
  180.                     currentPointNumber--;
  181.                 }
  182.                 if (arrayPoints[currentPointNumber] == down[i + 1]) {
  183.                     break;
  184.                 }
  185.                 while (added.size() >= 2 && vectorMult(added[added.size() - 2], added[added.size() - 1], arrayPoints[currentPointNumber]) <= 0) {
  186.                     added.erase(added.end());
  187.                 }
  188.                 if (arrayPoints[currentPointNumber] != down[i]) {
  189.                     added.push_back(arrayPoints[currentPointNumber]);
  190.                 }
  191.                 currentPointNumber--;
  192.             }
  193.             int squareTmp = -vectorMult(shell[0], down[i - 1], down[i]) - vectorMult(shell[0], down[i], down[i + 1]);
  194.             while (added.size() >= 2 && vectorMult(added[added.size() - 2], added[added.size() - 1], arrayPoints[currentPointNumber]) <= 0) {
  195.                 added.erase(added.end());
  196.             }
  197.             added.push_back(down[i + 1]);
  198.             for (int j = 1; j < added.size(); ++j) {
  199.                 squareTmp += vectorMult(shell[0], added[j - 1], added[j]);
  200.             }
  201.             answer = min(answer, sum + squareTmp);
  202.             while (arrayPoints[currentPointNumber] != down[i]) {
  203.                 currentPointNumber++;
  204.             }
  205.         }
  206.  
  207.         //обработка двух крайних точек
  208.         vector<point> tmp = arrayPoints;
  209.         arrayPoints.erase(arrayPoints.begin());
  210.         //первая точка
  211.         {
  212.             vector<point> upTmp, downTmp;
  213.             upTmp.push_back(arrayPoints[0]);
  214.             upTmp.push_back(arrayPoints[1]);
  215.             downTmp.push_back(arrayPoints[arrayPoints.size() - 1]);
  216.             downTmp.push_back(arrayPoints[arrayPoints.size() - 2]);
  217.             for (int i = 2; i < arrayPoints.size(); ++i) {
  218.                 while (upTmp.size() >= 2 && vectorMult(upTmp[upTmp.size() - 2], upTmp[upTmp.size() - 1], arrayPoints[i]) <= 0) {
  219.                     upTmp.erase(upTmp.end());
  220.                 }
  221.                 upTmp.push_back(arrayPoints[i]);
  222.             }
  223.  
  224.             for (int i = arrayPoints.size() - 2; i >= 0; --i) {
  225.                 while (downTmp.size() >= 2 && vectorMult(downTmp[downTmp.size() - 2], downTmp[downTmp.size() - 1], arrayPoints[i]) <= 0) {
  226.                     downTmp.erase(downTmp.end());
  227.                 }
  228.                 downTmp.push_back(arrayPoints[i]);
  229.             }
  230.  
  231.             vector<point> shellTmp;
  232.             shellTmp = upTmp;
  233.             for (int i = 1; i < downTmp.size() - 1; ++i) {
  234.                 shellTmp.push_back(downTmp[i]);
  235.             }
  236.  
  237.             answer = min(square(shellTmp), answer);
  238.         }
  239.         arrayPoints = tmp;
  240.         //последняя точка
  241.         arrayPoints.erase(arrayPoints.end());
  242.         {
  243.             vector<point> upTmp, downTmp;
  244.             upTmp.push_back(arrayPoints[0]);
  245.             upTmp.push_back(arrayPoints[1]);
  246.             downTmp.push_back(arrayPoints[arrayPoints.size() - 1]);
  247.             downTmp.push_back(arrayPoints[arrayPoints.size() - 2]);
  248.             for (int i = 2; i < arrayPoints.size(); ++i) {
  249.                 while (upTmp.size() >= 2 && vectorMult(upTmp[upTmp.size() - 2], upTmp[upTmp.size() - 1], arrayPoints[i]) <= 0) {
  250.                     upTmp.erase(upTmp.end());
  251.                 }
  252.                 upTmp.push_back(arrayPoints[i]);
  253.             }
  254.  
  255.             for (int i = arrayPoints.size() - 2; i >= 0; --i) {
  256.                 while (downTmp.size() >= 2 && vectorMult(downTmp[downTmp.size() - 2], downTmp[downTmp.size() - 1], arrayPoints[i]) <= 0) {
  257.                     downTmp.erase(downTmp.end());
  258.                 }
  259.                 downTmp.push_back(arrayPoints[i]);
  260.             }
  261.  
  262.             vector<point> shellTmp;
  263.             shellTmp = upTmp;
  264.             for (int i = 1; i < downTmp.size() - 1; ++i) {
  265.                 shellTmp.push_back(downTmp[i]);
  266.             }
  267.  
  268.             answer = min(square(shellTmp), answer);
  269.         }
  270.         cout << fixed << setprecision(2) << double(answer) / 2 << endl;
  271.         cin >> n;
  272.     }
  273.     return 0;
  274.  
  275. }
  276.  
  277. point::point(int x, int y) {
  278.     this->x = x;
  279.     this->y = y;
  280. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement