Advertisement
Guest User

Untitled

a guest
Dec 16th, 2013
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.08 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. struct vec2d {
  10.     int x, y;
  11.  
  12.     inline void init(int x, int y) {
  13.         this->x = x;
  14.         this->y = y;
  15.     }
  16.  
  17.     vec2d(int x, int y) {
  18.         init(x, y);
  19.     }
  20.  
  21.     vec2d() {}
  22.  
  23.     inline int cross(const vec2d &b) const {
  24.         return x * b.y - b.x * y;
  25.     }
  26.  
  27.     inline int operator%(const vec2d &b) const {
  28.         return cross(b);
  29.     }
  30.  
  31.     inline int sqlen() const {
  32.         return x * x + y * y;
  33.     }
  34.  
  35.     inline double len() const {
  36.         return sqrt((double)sqlen());
  37.     }
  38.  
  39.     inline vec2d operator-(const vec2d& b) const {
  40.         return vec2d(x - b.x, y - b.y);
  41.     }
  42. };
  43.  
  44. // x1*y2 - x2*y1
  45. int n;
  46. vec2d a[20000];
  47. vector<vec2d> s;
  48.  
  49. bool comp(const vec2d &a, const vec2d &b) {
  50.     int q = a % b;
  51.     if (q != 0) {
  52.         return q > 0;
  53.     }
  54.     return a.sqlen() < b.sqlen();
  55. }
  56.  
  57. int main() {
  58.     //freopen("input.txt", "r", stdin);
  59.     //freopen("output.txt", "w", stdout);
  60.     //cout << vec2d(1, 1).cross(vec2d(1, 0)) << endl;
  61.     cin >> n;
  62.     int shx = 100500, shy = 100500;
  63.     for (int i = 0; i < n; ++i) {
  64.         cin >> a[i].x >> a[i].y;
  65.         if (a[i].y < shy) {
  66.             shy = a[i].y;
  67.             shx = a[i].x;
  68.         }
  69.         if (a[i].x < shx && a[i].y == shy) {
  70.             shx = a[i].x;
  71.         }
  72.     }
  73.     //cout << "shift by" << shx << " " << shy << endl;
  74.     for (int i = 0; i < n; ++i) {
  75.         a[i].x -= shx;
  76.         a[i].y -= shy;
  77.     }
  78.     sort(a, a + n, comp);
  79.     for (int i = 0; i < n; ++i) {
  80.         unsigned k;
  81.         while ((k = s.size()) >= 2 && (s[k - 1] - s[k - 2]) % (a[i] - s[k - 1]) <= 0) {
  82.             s.pop_back();
  83.         }
  84.         s.push_back(a[i]);
  85.     }
  86.     /*for (unsigned i = 0; i < s.size(); ++i) {
  87.         cout << s[i].x << " " << s[i].y << "\n";
  88.     }*/
  89.     s.push_back(s.front());
  90.  
  91.     double p = 0;
  92.     for (unsigned i = 1; i < s.size(); ++i) {
  93.         p += (s[i - 1] - s[i]).len();
  94.         //cout << ":" << "(" << a[i].x << ", " << a[i].y << ")" <<  (a[i - 1] - a[i]).len() << " ";
  95.     }
  96.     cout << p << endl;
  97.  
  98.     long long sq2 = 0;
  99.     for (unsigned i = 1; i < s.size(); ++i) {
  100.         sq2 += (s[i - 1].x - s[i].x) * (s[i - 1].y + s[i].y);
  101.     }
  102.     cout << sq2 / 2 << (sq2 % 2? ".5" : "") << endl;
  103.     //cout << sq2 << endl;
  104.  
  105.     return 0;
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement