Advertisement
Guest User

Untitled

a guest
Mar 23rd, 2018
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.81 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <utility>
  4. #include <ctime>
  5. #include <cctype>
  6. #include <cstdlib>
  7. #include <cassert>
  8. #include <functional>
  9. #include <algorithm>
  10. #include <cmath>
  11. #include <vector>
  12. #include <map>
  13. #include <set>
  14. #include <iomanip>
  15. #include <string>
  16. #include <stack>
  17. #include <queue>
  18. #include <bitset>
  19. #include <fstream>
  20. using namespace std;
  21.  
  22. struct pt {
  23.     int x, y;
  24. };
  25.  
  26. bool cmp (pt a, pt b) {
  27.     return a.x < b.x || (a.x == b.x && a.y < b.y);
  28. }
  29.  
  30. bool cw (pt a, pt b, pt c) {
  31.     return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
  32. }
  33.  
  34. bool ccw (pt a, pt b, pt c) {
  35.     return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
  36. }
  37.  
  38.  
  39. double square(pt pt1, pt pt2, pt pt3) {
  40.     double s = abs(0.5*((pt1.x - pt3.x)*(pt2.y - pt3.y) - (pt2.x - pt3.x)*(pt1.y - pt3.y)));
  41.     return s;
  42. }
  43.  
  44. double dist (pt pt1, pt pt2, pt pt3) {
  45.     int a = pt1.y - pt2.y;
  46.     int b = pt1.x - pt2.x;
  47.     int c = -pt1.x * (pt2.y - pt1.y) + pt1.y * (pt2.x - pt1.x);
  48.    // ะก = -X1* (Y2 โ€“ Y1) + Y1*(X2 โ€“X1)
  49.    
  50.     return (abs(a*pt3.x + b*pt3.y + c) / sqrt (a*a + b*b));
  51. }
  52.  
  53. double Fsquare (const vector<pt> & fig)
  54. {
  55.     double res = 0;
  56.     for (unsigned i=0; i<fig.size(); i++)
  57.     {
  58.         pt p1 = i ? fig[i-1] : fig.back(),
  59.            p2 = fig[i];
  60.         res += (p1.x - p2.x) * (p1.y + p2.y);
  61.     }
  62.     return fabs (res) / 2;
  63. }
  64.  
  65. vector <pt> exter, inter, unused, allpt, used;
  66. pt last;
  67.  
  68. void convex_hull (vector <pt> & a) {
  69.    
  70.     if (a.size() == 1)  return;
  71.    
  72.     sort (a.begin(), a.end(), &cmp);
  73.     pt p1 = a[0],  p2 = a.back();
  74.     vector <pt> up, down;
  75.     up.push_back (p1);
  76.     down.push_back (p1);
  77.     for (size_t i=1; i < a.size(); ++i) {
  78.         if (i==a.size()-1 || cw (p1, a[i], p2)) {
  79.             while (up.size() >= 2 && !cw (up[up.size()-2], up[up.size()-1], a[i])){
  80.                 last = up [up.size() - 1];
  81.                 unused.push_back (last);
  82.                 up.pop_back();
  83.             }
  84.             up.push_back (a[i]);
  85.         }
  86.         if (i==a.size()-1 || ccw (p1, a[i], p2)) {
  87.             while (down.size() >= 2 && !ccw (down[down.size()-2], down[down.size()-1], a[i])) {
  88.                 last = down [down.size() - 1];
  89.                 unused.push_back (last);
  90.                 down.pop_back();
  91.             }
  92.             down.push_back (a[i]);
  93.         }
  94.     }
  95.     a.clear();
  96.     for (size_t i = 0; i < up.size(); ++i)
  97.         a.push_back (up[i]);
  98.     for (size_t i = down.size() - 2; i > 0; --i)
  99.         a.push_back (down[i]);
  100.    
  101.     up.clear(); down.clear();
  102. }
  103.  
  104.  
  105. int main() {
  106.     ios_base::sync_with_stdio(0);
  107.     cin.tie(0); cout.tie(0);
  108.    
  109.     int n; cin >> n;
  110.  
  111.     for (int i = 0; i < n; ++i) {
  112.         int x, y;
  113.         pt p;
  114.         cin >> x >> y;
  115.         p.x = x; p.y = y;
  116.         allpt.push_back(p);
  117.         exter.push_back(p);
  118.     }
  119.  
  120.     convex_hull(exter);
  121.  
  122.     if (exter.size() == n) {
  123.         cout << -1;
  124.         return 0;
  125.     }
  126.  
  127.     cout << "exter" << '\n';
  128.     for (pt now: exter) {
  129.         cout << now.x << " " << now.y << '\n';
  130.     }
  131.  
  132.     bool flag = true, check1 = true;
  133.     for (int j = 0; j < unused.size(); ++j) {
  134.         for (int i = 0; i < exter.size()-1; ++i) {
  135.             if (square (exter[i], exter[i+1], unused[j]) == 0) {
  136.                 used.push_back(unused[j]);
  137.                 flag = false;
  138.                 break;
  139.             }
  140.         }
  141.         if (flag)  {
  142.             inter.push_back(unused[j]);
  143.             check1 = false;
  144.         }
  145.     }
  146.    
  147.     if (check1) {
  148.         cout << -1;
  149.         return 0;
  150.     }
  151.    
  152.     convex_hull(inter);
  153.    
  154.     cout << "inter" << '\n';
  155.    
  156.     for (pt now: inter) {
  157.         cout << now.x << " " << now.y << '\n';
  158.     }
  159.    
  160.     cout << "used" << '\n';
  161.    
  162.     for (pt now: used) {
  163.         cout << now.x << " " << now.y << '\n';
  164.     }
  165.    
  166.  
  167.     double fS = Fsquare (exter);
  168.    
  169.     cout << "Full " << fS << '\n';
  170.    
  171.    
  172.     double temp = 1e9;
  173.     int fixL;
  174.     int m = exter.size();
  175.    
  176.         for (int i = 0; i < exter.size(); ++i) {
  177.             double S = square(exter[i%m], exter[(i+1)%m], inter[0]);
  178.             if (S < temp && S != 0) {
  179.                 fixL = i;
  180.                 temp = square(exter[i%m], exter[(i+1)%m], inter[0]);
  181.             }
  182.         }
  183.     double ans = 1e9;
  184.     for (int i = 1; i < inter.size(); ++i) {
  185.         ans = min(ans, temp);
  186.         int k = fixL;
  187.         while (square (exter[(k+1)%m], exter[(k+2)%m], inter[i]) < temp){
  188.             ++k;
  189.         }
  190.         if (square (exter[k%m], exter[(k+1)%m], inter[i]) != 0)  {
  191.             temp = square (exter[k%m], exter[(k+1)%m], inter[i]);
  192.             fixL = k;
  193.         }
  194.        
  195.     }
  196.    
  197.     ans = min(ans, temp);
  198.     temp = ans;
  199.    
  200.     cout << "Part " << temp << '\n';
  201.     cout << 2*(fS - temp);
  202.    
  203.    
  204.     return 0;
  205. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement