Advertisement
Guest User

Untitled

a guest
Apr 20th, 2018
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <set>
  5. #include <map>
  6. #include <stack>
  7. #include <queue>
  8. #include <deque>
  9. #include <ctime>
  10. #include <random>
  11. #include <cmath>
  12. #include <bitset>
  13. #include <iomanip>
  14. #include <list>
  15.  
  16. using namespace std;
  17.  
  18. typedef long long ll;
  19.  
  20. struct point {
  21.     ll x, y;
  22.     point() : x(0), y(0) {}
  23.     point(ll xx, ll yy) {
  24.         x = xx;
  25.         y = yy;
  26.     }
  27.     void scan() {
  28.         cin >> x >> y;
  29.     }
  30.     void print() {
  31.         cout << x << " " << y << "\n";
  32.     }
  33.     ll operator*(const point &p) const {
  34.         return x * p.x + y * p.y;
  35.     }
  36.     ll operator%(const point &p) const {
  37.         return x * p.y - y * p.x;
  38.     }
  39.     bool operator==(const point &p) const {
  40.         return x == p.x && y == p.y;
  41.     }
  42.     point operator-(const point &p) const {
  43.         return point(x - p.x, y - p.y);
  44.     }
  45.     point operator+(const point &p) const {
  46.         return point(x + p.x, y + p.y);
  47.     }
  48.     bool is_on_line(point &A, point &B) {
  49.         return (((A - *this) % (B - *this)) == 0);
  50.     }
  51.     bool is_on_segment(point &A, point &B) {
  52.         return (*this).is_on_line(A, B) && ((A - *this) * (B - *this) <= 0);
  53.     }
  54.     double length() {
  55.         return sqrt(double((*this) * (*this)));
  56.     }
  57.     ll sqr_len() {
  58.         return x * x + y * y;
  59.     }
  60.     double dist_to(const point &A, const point &B) const {
  61.         ll cur = abs((A - *this) % (B - *this));
  62.         return (double)cur / (A - B).length();
  63.     }
  64.  
  65. };
  66.  
  67. int main() {
  68.     ios_base::sync_with_stdio(false);
  69.     cin.tie(0);
  70.     #ifndef ONLINE_JUDGE
  71.     freopen("input.txt", "r", stdin);
  72.     freopen("output.txt", "w", stdout);
  73.     #endif
  74.     int n;
  75.     cin >> n;
  76.     vector <point> polygon(n);
  77.     for (int i = 0; i < n; ++i) {
  78.         polygon[i].scan();
  79.     }
  80.     for (int i = 1; i < n; ++i) {
  81.         if (polygon[i].x < polygon[0].x || (polygon[i].x == polygon[0].x && polygon[i].y < polygon[0].y)) {
  82.             swap(polygon[0], polygon[i]);
  83.         }
  84.     }
  85.     sort(polygon.begin() + 1, polygon.end(), [&](const point &s, const point &f) {
  86.         if((s - polygon[0]) % (f - polygon[0]) != 0) {
  87.             return (s - polygon[0]) % (f - polygon[0]) > 0;
  88.         }
  89.         else {
  90.             return (s - polygon[0]).sqr_len() < (f - polygon[0]).sqr_len();
  91.         }
  92.     });
  93.  
  94.     vector <point> s;
  95.     s.push_back(polygon[0]);
  96.     s.push_back(polygon[1]);
  97.     for (int i = 2; i < n; ++i) {
  98.         while (s.size() > 1 && (s[s.size() - 2] - s.back()) % (polygon[i] - s.back()) >= 0) {
  99.             s.pop_back();
  100.         }
  101.         s.push_back(polygon[i]);
  102.     }
  103.     double P = 0;
  104.     double S = 0;
  105.     s.push_back(s[0]);
  106.     for (int i = 0; i + 1 < s.size(); ++i) {
  107.         P += (s[i + 1] - s[i]).length();
  108.         S += s[i] % s[i + 1];
  109.     }
  110.     S /= 2;
  111.     S = abs(S);
  112.     cout << fixed << setprecision(16) << P << endl << S << endl;
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement