simonmadson

Untitled

Feb 25th, 2018
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.94 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef long double ld;
  7.  
  8. long long inf = 1e16;
  9.  
  10. struct vec {
  11.     ll x, y;
  12.  
  13.     vec() {
  14.         x = rand() % 20000 - 10000;
  15.         y = rand() % 20000 - 10000;
  16.     }
  17.  
  18.     vec(ll a, ll b) {
  19.         x = a, y = b;
  20.     }
  21.  
  22.     vec(vec a, vec b) {
  23.         x = b.x - a.x;
  24.         y = b.y - a.y;
  25.     }
  26.  
  27.     void make_vec(vec a, vec b) {
  28.         x = b.x - a.x;
  29.         y = b.y - a.y;
  30.     }
  31. };
  32.  
  33. istream& operator >>(istream& in, vec &a) {
  34.     in >> a.x >> a.y;
  35.     return in;
  36. }
  37.  
  38. ostream& operator <<(ostream& os, vec &a) {
  39.     os << a.x << ' ' << a.y;
  40.     return os;
  41. }
  42.  
  43. ll operator ^(vec a, vec b) {
  44.     return a.x * b.y - a.y * b.x;
  45. }
  46.  
  47. ll operator *(vec a, vec b) {
  48.     return a.x * b.x + a.y * b.y;
  49. }
  50.  
  51. vec start;
  52.  
  53. bool cmp1(vec a, vec b) {
  54.     return a.y < b.y || a.y == b.y && a.x < b.x;
  55. }
  56.  
  57. bool cmp2(vec a, vec b) {
  58.     vec f(start, a), s(start, b);
  59.     return ((f ^ s) > 0) || ((f ^ s) == 0 && (a * a < b * b));
  60. }
  61.  
  62. string solve1(vector<vec> p) {
  63.     sort(p.begin(), p.end(), cmp1);
  64.     start = p[0];
  65.     sort(p.begin() + 1, p.end(), cmp2);
  66.  
  67.     vector <vec> cnv;
  68.  
  69.     for (int i = 0; i < p.size(); ++i) {
  70.         while (cnv.size() > 1) {
  71.             vec a(cnv[cnv.size() - 2], cnv[cnv.size() - 1]),
  72.                 b(cnv[cnv.size() - 2], p[i]);
  73.             if ((a ^ b) <= 0)
  74.                 cnv.pop_back();
  75.             else
  76.                 break;
  77.         }
  78.         cnv.push_back(p[i]);
  79.     }
  80.    
  81.     cnv.push_back(start);
  82.     vec o(0, 0);
  83.     ld per = 0, ar = 0;
  84.     for (int i = 0; i < cnv.size() - 1; ++i) {
  85.         vec e(cnv[i], cnv[i + 1]);
  86.         per += sqrt(e * e);
  87.  
  88.         vec a(o, cnv[i]),
  89.             b(o, cnv[i + 1]);
  90.         ar += (a ^ b);
  91.     }
  92.     string s = "";
  93.     ostringstream os(s);
  94.     os << fixed << setprecision(10);
  95.     os << per << '\n' << fabsl(ar / 2.0);
  96.     return os.str();
  97. }
  98.  
  99. #define pb push_back
  100. #define ppb pop_back
  101. #define double long double
  102. #define int long long
  103.  
  104. const double eps = 1e-9;
  105.  
  106. struct point {
  107.     int x, y;
  108.     point(){}
  109.     point(int x, int y) : x(x), y(y) {}
  110. };
  111.  
  112. struct Vector {
  113.     int x, y;
  114.     Vector(){}
  115.     Vector(point a, point b) {
  116.         x = b.x-a.x;
  117.         y = b.y-a.y;
  118.     }
  119.     Vector(point a) {
  120.         x = a.x;
  121.         y = a.y;
  122.     }
  123. };
  124.  
  125. istream& operator >> (istream& is, point& p) {
  126.     is >> p.x >> p.y;
  127.     return is;
  128. }
  129.  
  130. bool cmp(point a, point b) {
  131.     return a.x < b.x || a.x == b.x && a.y < b.y;
  132. }
  133.  
  134. int operator * (Vector a, Vector b) {
  135.     return a.x*b.x+a.y*b.y;
  136. }
  137.  
  138. int operator ^ (Vector a, Vector b) {
  139.     return a.x*b.y-a.y*b.x;
  140. }
  141.  
  142. bool cw(point a, point b, point c) {
  143.     return (Vector(a, b)^Vector(a, c)) < 0;
  144. }
  145.  
  146. bool ccw(point a, point b, point c) {
  147.     return (Vector(a, b)^Vector(a, c)) > 0;
  148. }
  149.  
  150. vector<point> convex_hull(vector<point> v) {
  151.     vector<point> up, pu;
  152.     sort(v.begin(), v.end(), &cmp);
  153.     point p1 = v[0];
  154.     point p2 = v.back();
  155.     up.pb(p1); pu.pb(p1);
  156.     for (int i = 1; i < v.size(); ++i) {
  157.         point c = v[i];
  158.         if (cw(p1, c, p2) || i == v.size()-1) {
  159.             while(up.size() > 1 && !cw(up[up.size()-2], up[up.size()-1], c))
  160.                 up.ppb();
  161.             up.pb(c);
  162.         }
  163.         if (ccw(p1, c, p2) || i == v.size()-1) {
  164.             while(pu.size() > 1 && !ccw(pu[pu.size()-2], pu[pu.size()-1], c))
  165.                 pu.ppb();
  166.             pu.pb(c);
  167.         }
  168.     }
  169.     vector<point> ans;
  170.     for (int i = 0; i < up.size(); ++i) {
  171.         ans.pb(up[i]);
  172.     }
  173.     for (int i = pu.size()-2; i > 0; --i)
  174.         ans.pb(pu[i]);
  175.     return ans;
  176. }
  177.  
  178. double dist(point a, point b) {
  179.     double x = b.x-a.x;
  180.     double y = b.y-a.y;
  181.     return sqrt(x*x+y*y);
  182. }
  183.  
  184.  
  185. string solve2(vector<point> v) {
  186.     vector<point> hull = convex_hull(v);
  187.     double per = dist(hull[0], hull.back());
  188.     for (int i = 1; i < hull.size(); ++i) {
  189.         per += dist(hull[i], hull[i-1]);
  190.     }
  191.     double sq = (Vector(hull.back())^Vector(hull[0]));
  192.     // cout << sq << endl;
  193.     for (int i = 1; i < hull.size(); ++i) {
  194.         sq += Vector(hull[i-1])^Vector(hull[i]);
  195.         // cout << sq << endl;
  196.     }
  197.     string s = "";
  198.     ostringstream os(s);
  199.     os << fixed << setprecision(10) << per << endl << abs(sq*0.5);
  200.     return os.str();
  201. }
  202. int32_t main() {
  203.     srand(time(NULL));
  204.     for (int i = 0; i < 10000; ++i) {
  205.         int n = rand() % 10 + 1;
  206.         vector <vec> p(n);
  207.         for (int i = 0; i < n; ++i) {
  208.             p[i] = vec();
  209.         }
  210.         vector<point> v(n);
  211.         for (int i = 0; i < n; ++i) {
  212.             v[i] = point(p[i].x, p[i].y);
  213.         }
  214.         string ans1 = solve1(p);
  215.         string ans2 = solve2(v);
  216.         if (ans1 != ans2) {
  217.             cout << "ALERTALERT\n";
  218.             cout << n << endl;
  219.             for (auto vv : p) {
  220.                 cout << vv << endl;
  221.             }
  222.             cout << endl;
  223.         }
  224.     }
  225.     return 0;
  226. }
Advertisement
Add Comment
Please, Sign In to add comment